ICPC Dhaka Preli 2017: Problem D - Connecting To One solution

সমস্যাঃ

$N$ নোড ও $E$ এজ বিশিষ্ট একটি গ্রাফ দেয়া আছে, যার প্রতিটা এজের ওয়েট (cost) বলে দেয়া আছে ।

এরপরে $Q$ সংখ্যক কুয়েরি দেয়া আছে । প্রতিটা কুয়েরিতে একটি নাম্বার $C$ দেয়া আছে । বলতে হবে, যেসব এজের ওয়েট $C$ এর কম, সেই এজগুলিকে যদি গ্রাফ থেকে মুছে দেয়া হয়, তবে ১ নাম্বার নোড থেকে কতগুলি নোডে যাওয়া সম্ভব ।

Constraints:

1. ইনপুটে সর্বোচ্চ ১০ টি টেস্ট কেস দেয়া থাকবে ।
2. $1\leq \space N \space \leq 40,000$
3. $1\leq \space E \space \leq 150,000$
4. $1\leq \space |W| \space \leq 10^9$, W বলতে এজের ওয়েট বুঝানো হচ্ছে ।
5. $1\leq \space Q \space \leq 10^5$
6. $1\leq \space |C| \space \leq 10^9$

সমাধানঃ

আমরা কোন গ্রাফ তৈরি করব না । 

এজগুলি ইনপুট নিয়ে ওয়েটের Descending order এ সর্ট করব ।

এরপরে সবগুলো কুয়েরি ইনপুট নিয়ে তাদেরকেও Descending order এ সর্ট করব । এরপরে আমরা কুয়েরি গুলি অফলাইনে প্রসেস করব । এক্ষেত্রে পরে যেহেতু আমাদের কুয়েরির ইন্ডেক্স প্রয়োজন হবে, তাই ইন্ডেক্স সহ রেখে ( যেমন pair<int, int> হিসেবে ) সর্ট করতে হবে ।

এখন সর্ট করা এজগুলি থেকে একটি করে এজ নিয়ে ঐ এজের নোড দুটিকে ডিসজয়েন্ট সেটে যুক্ত করব। সাথে এখন পর্যন্ত সেটে রাখা এজগুলির মাঝে সবচেয়ে কম ওয়েট কত তা একটি ভেরিয়েবলে (minCost) রাখব ।

আর পাশাপাশি সর্টেড কুয়েরি লিস্টের কোন কুয়েরিকে প্রসেস করছি, তার ইন্ডেক্স একটা ভেরিয়েবলে (curQ)রাখব ।

প্রতিটা এজ থেকে নোড দুটিকে ডিসজয়েন্ট সেটে যুক্ত করার পরে যদি এই এজের ওয়েট টা minCost এর চেয়ে ছোট হয়, তবে minCost এর ভ্যালুকে এই ওয়েট দিয়ে আপডেট করব ।

এরপরে দেখব, যদি minCost এর ভ্যালু curQ তম কুয়েরি তে C এর মান এর চেয়েও ছোট হয়, তবে যতক্ষণ curQ < Q এবং minCost বর্তমান যে কুয়েরিকে প্রসেস করছি তার C এর মানের চেয়ে ছোট হয়, ততক্ষণ curQ এর মান কে 1 করে বাড়াব, মানে কুয়েরির ইন্ডেক্স কে এক বাড়াব এবং আরো ডানে যাব ।

কেন ?

কারণ, এখন পর্যন্ত যুক্ত করা এজ গুলির মাঝে সর্বনিম্ন ওয়েট হলো minCost.

কিন্তু যেসব কুয়েরিতে এর চেয়েও বড় ওয়েট(C) দিয়ে কুয়েরি করা হয়েছে, সেখানে C এর চেয়ে ছোট সব এজ গ্রাফ থেকে মুছে যাবে । তাই কুয়েরির জন্য উত্তর হবে ০ (শুণ্য) । যেহেতু কুয়েরি গুলিকে Descending order এ সাজানো আছে, তাই C এর চেয়ে ছোট ভ্যালু দিয়ে কুয়েরি করা হয়েছে সেরকম কুয়েরি পেতে আমাদেরকে আরো ডান দিকে যেতে হবে ।

১ম যে পজিশনে কুয়েরির ভ্যালু(C), minCost এর চেয়ে ছোট বা সমান হবে, সেই কুয়েরির উত্তর হবে আমাদের ১ নাম্বার নোডের সাথে যুক্ত থাকা নোড গুলোর সেটের সাইজ ।

curQ তম ইন্ডেক্সের ans যত, যতক্ষণ curQ কে বাড়াচ্ছি, তার মাঝের এই ইন্ডেক্স গুলির ans ও হবে তাই ।

তাই তাদের ans কেও আপডেট করে দেব ।

কেন ?

কারণ, ৬ এর চেয়ে ছোট ওয়েটের এজ ডিলেট করলে ans যত হবে ৫ এর চেয়ে ছোট এজগুলিকে ডিলেট করলেও ans হয় তাই হবে, না হয় তার চেয়ে বেশি হবে, কিন্তু কম হবে না কখনো । কিন্তু এখানে মাঝের এসব ইন্ডেক্সের জন্য ans  বেশি হতে পারবে না, কারণ তাদের কুয়েরির ভ্যালু minCost এর চেয়ে ছোট না । 

১ম যেই কুয়েরি ইন্ডেক্সের ভ্যালু minCost এর চেয়ে ছোট বা সমান হবে সেই কুয়েরিতে এই বাড়তি এজ টা থাকতে পারবে । তার আগের গুলোতে এই জন্য আগের কুয়েরির ans টাই থাকবে । ans রাখার সময় কুয়েরি এর অরিজিনাল ইন্ডেক্সে ans টা ব্যবহার করে সেই ইন্ডেক্সে ans টা রাখব ।

এই অংশটা বুঝতে একটু খাতা কলম নিয়ে বসতে হবে, একটু চিন্তা করতে হবে । আর তাও না বুঝলে কমেন্টে জানালে আমি ব্যাখ্যা করব ।

সব এজ গুলোকে প্রসেস করা হয়ে গেলে আমাদের সব কুয়েরির জন্য ans পেয়ে যাব ।

এরপরে শুধু প্রতি টা কুয়েরির ans ইনপুট এর অর্ডারে প্রিন্ট করব - ব্যাস হয়ে গেল !!

কমপ্লেক্সিটি :  $O(E log E + Q log Q)$

কোডঃ

	/*=================================*\
	Md. Shahidul Islam
	CSE, BRUR
	Rangpur, Bangladesh
	mail: shahidul.cse.brur@gmail.com
	FB : fb.com/shahidul.brur
	Blog: shahidul-brur.blogspot.com
	\*=================================*/
	#include<bits/stdc++.h>
	using namespace std;
	const int MX = 100000;
	#define ii pair<int, int>
	int n, e;
	pair<int, ii > edge[MX+5];
	ii query[MX+5];
	int par[MX+5];
	int siz[MX+5];
	int ans[MX+5];
	int findPar(int u)
	{
	if(par[u]==u)
	return u;
	return par[u] = findPar(par[u]);
	}
	void makeUnion(int u, int v)
	{
	int pu = findPar(u);
	int pv = findPar(v);
	if(pu==pv) return;
	if(pu<pv)
	par[pv] = pu, siz[pu]+=siz[pv];
	else par[pu] = pv, siz[pv]+=siz[pu];
	}
	bool cmp(pair<int, ii > a, pair<int, ii > b)
	{
	if(a.first == b.first)
	{
	if(a.second.first==b.second.first)
	return a.second.second<b.second.second;
	return a.second.first<b.second.first;
	}
	return a.first>b.first;
	}
	bool cmp2(ii a, ii b)
	{
	if(a.first == b.first)
	{
	return a.second<b.second;
	}
	return a.first>b.first;
	}
	int main()
	{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	//ios_base::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	for(int cas = 1; cas<=t; cas++)
	{
	cin>>n>>e;
	for(int i = 1;i<=n;i++)
	par[i] = i, siz[i] = 1;
	for(int i = 0;i<e;i++)
	{
	int u, v, w;
	cin>>u>>v>>w;
	if(u>v)
	swap(u, v);
	edge[i].second.first = u;
	edge[i].second.second = v;
	edge[i].first = w;
	}
	sort(edge, edge+e, cmp);
	int q;
	cin>>q;
	for(int i = 0;i<q;i++)
	{
	int C;
	cin>>C;
	query[i].first = C;
	query[i].second = i;
	ans[i] = 0;
	}
	sort(query, query+q, cmp2);
	int minCost = (int)1e9+100;
	int curQ = 0;
	for(int i = 0;i<e;i++)
	{
	int w = edge[i].first;
	int u = edge[i].second.first;
	int v = edge[i].second.second;
	makeUnion(u, v);
	minCost = min(minCost, w);
	while(curQ+1<q && minCost<query[curQ].first)
	{
	ans[ans[query[curQ+1].second]] = ans[query[curQ].second];
	curQ++;
	}
	if(curQ==q)
	break;
	ans[query[curQ].second] = siz[1] - 1;
	}
	cout << "Case " << cas << ":\n";
	for(int i = 0;i<q;i++)
	cout << ans[i] << "\n";
	}
	return 0;
	}

view raw solution.cpp hosted with ❤ by GitHub