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)$

কোডঃ