Advertisement
Guest User

Untitled

a guest
Apr 2nd, 2016
180
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAXN 300010
  5.  
  6. int N, a, b;
  7. vector< int >colleg[MAXN];
  8. bool visited[MAXN];
  9. int scelta[MAXN];
  10.  
  11. int Dfs(int n, int verso) {
  12.     visited[n]=true;
  13.     if(n == verso) return scelta[n] = n;
  14.    
  15.     for(int i : colleg[n]) {
  16.         if(visited[i]) continue;
  17.         int tmp = Dfs(i, verso);
  18.         if(tmp > -1) { scelta[n] = i; break; }
  19.     }
  20.    
  21.     return scelta[n];
  22. }
  23.  
  24. int Colora(int rad, pair<int, int>bloccato) {
  25.     visited[rad]=true;
  26.     vector< int >cosi;
  27.     for(int i : colleg[rad]) {
  28.         if( (make_pair(rad, i) ==bloccato) || (make_pair(i, rad)==bloccato) ) continue;
  29.         if(visited[i]) continue;
  30.         cosi.push_back(1 + Colora(i, bloccato));
  31.     }
  32.    
  33.     sort(cosi.begin(), cosi.end());
  34.     reverse(cosi.begin(), cosi.end());
  35.    
  36.     int ris=0;
  37.     for(int i=0;i<(int)cosi.size();i++) ris=max(ris, i + cosi[i]);
  38.    
  39.     return ris;
  40. }
  41.  
  42. pair<int, int> Controlla(pair<int, int>arco) {
  43.     memset(visited, false, sizeof visited);
  44.     int ans1 = Colora(a, arco);
  45.        
  46.     memset(visited, false, sizeof visited);
  47.     int ans2 = Colora(b, arco);
  48.     return {ans1, ans2};
  49. }
  50. int main() {
  51.     ios::sync_with_stdio(0);
  52.     cin.tie(0);
  53.     cout.tie(0);
  54.    
  55.     cin >> N >> a >> b;
  56.     int p, q;
  57.     for(int i=0;i<N-1;i++) {
  58.         cin>>p>>q;
  59.         colleg[p].push_back(q);
  60.         colleg[q].push_back(p);
  61.     }
  62.        
  63.     memset(scelta, -1, sizeof scelta);
  64.     Dfs(a, b);
  65.        
  66.     vector< pair<int, int> >v;
  67.     int parto = a;
  68.     while(parto != b) v.push_back({parto, scelta[parto]}), parto=scelta[parto];
  69.    
  70.    
  71.     int ris = -1;
  72.     int low=0, high=(int)v.size() - 1, mid=0;
  73.     while(low <= high) {
  74.         mid= (low+high)/2;
  75.         pair<int, int> tmp_ans = Controlla(v[mid]);
  76.         int tmp_a = tmp_ans.first, tmp_b = tmp_ans.second;
  77.         pair<int, int> avanti = ((mid+1 >= (int)v.size()) ? make_pair(-1,-1) : Controlla(v[mid+1]));
  78.        
  79.         ris=(ris==-1) ? max(tmp_a, tmp_b) : min(ris, max(tmp_a, tmp_b));
  80.         if(avanti.first==-1) break;
  81.        
  82.         if(max(tmp_a, tmp_b) > max(avanti.first, avanti.second)) low=mid+1;
  83.         else if(max(tmp_a, tmp_b) > max(avanti.first, avanti.second)) high=mid-1;
  84.         else {
  85.             if(tmp_a < tmp_b) low=mid+1;
  86.             else high=mid-1;
  87.            
  88.             /* if(tmp_a <= tmp_b) low=mid+1;
  89.              * else high=mid-1;
  90.             */
  91.         }
  92.     }
  93.    
  94.     cout << ris << endl;
  95.     return EXIT_SUCCESS;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement