At Coder - Grand Contest 001 - Shorten Diameter Tutorial
Problem Description here
প্রবলেমঃ প্রবলেমটিতে মূলত বলা হয়েছে, n সংখ্যক নোডের একটি ট্রি দেয়া থাকবে। সর্বনিম্ন কতগুলো নোড বাদ দিলে ট্রি এর ডায়ামিটার সর্বোচ্চ k হবে।
একটি ট্রি এর ডায়ামিটার বলতে বুঝানো হয় ট্রি এর যেকোন দুইটি নোডের মধ্যবর্তী দূরত্বগুলোর সর্বোচ্চ মান।
সল্যুশন আইডিয়াঃ
১) প্রতিটি ডায়ামিটার এর একটা সেন্টার থাকে। সেন্টার থেকে দুইদিকের দূরত্ব সমান হয়।
২) ডায়ামিটার এর দৈর্ঘ্য জোড় হলে সেন্টার হবে একটা নোড। আর বিজোড় হলে সেন্টার হবে একটা এজ।
৩) এখন, ট্রি এর প্রতিটি নোড অথবা এজকে (k এর মান এর উপর নির্ভর করে) ডায়ামিটার এর সেন্টার ধরে দেখবো এই নোড বা এজ সেন্টার হলে কতগুলো নোড রাখা যায় অথবা কতগুলো নোড বাদ দিতে হয়?
এভাবে, প্রতিটি নোড হিসেব করে সর্বনিম্ন কয়টা বাদ দেয়া যায় সেটা বের করা সম্ভব।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| #define scin(x) sc("%d",&(x)) | |
| #define scin2(x,y) sc("%d %d",&(x),&(y)) | |
| #define ms(a,b) memset(a,b,sizeof(a)) | |
| #define pb(a) push_back(a) | |
| #define vi vector<int> | |
| #define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++) | |
| using namespace std; | |
| #define sz 2005 | |
| vi graph[sz]; | |
| int n,k,bad=0,vis[sz],level[sz],parent[sz]; | |
| void DFS(int u,int par) | |
| { | |
| vis[u] = 1; | |
| parent[u] = par; | |
| for(auto v:graph[u]){ | |
| if(!vis[v]) | |
| DFS(v , u); | |
| } | |
| } | |
| void DFS2(int u,int lev,int opposite) | |
| { | |
| vis[u] = 1; | |
| level[u] = lev; | |
| if(level[u] > k/2){ | |
| bad++; | |
| } | |
| for(auto v:graph[u]){ | |
| if(!vis[v] && v!=opposite) | |
| DFS2(v , 1+lev , opposite); | |
| } | |
| } | |
| void Solve(int t) | |
| { | |
| int i,j,u,v,ans; | |
| scin2(n , k); | |
| for(i=1 ; i<=n-1 ; i++){ | |
| scin2(u , v); | |
| graph[u].pb(v); | |
| graph[v].pb(u); | |
| } | |
| if(k == 1){ | |
| cout<<n-2<<endl; | |
| return; | |
| } | |
| else | |
| ans = n; | |
| DFS(1 , -1); | |
| if(k%2 == 0){ | |
| for(i=1 ; i<=n ; i++){ | |
| ms(vis , 0); | |
| bad = 0; | |
| DFS2(i , 0 , -1); | |
| ans = min(ans , bad); | |
| } | |
| } | |
| else{ | |
| for(i=1 ; i<=n ; i++){ | |
| u = i; | |
| v = parent[i]; | |
| if(v != -1){ | |
| ms(vis , 0); | |
| bad = 0; | |
| DFS2(u , 0 , v); | |
| DFS2(v , 0 , u); | |
| ans = min(ans , bad); | |
| } | |
| } | |
| } | |
| cout<<ans<<endl; | |
| } | |
| int main() | |
| { | |
| int t,T; | |
| T = 1; | |
| RUN_CASE(t,T) | |
| { | |
| Solve(t); | |
| } | |
| return 0; | |
| } | |
Comments
Post a Comment