Submission #127877

#TimeUsernameProblemLanguageResultExecution timeMemory
127877Adhyyan1252Torrent (COI16_torrent)C++11
100 / 100
446 ms28040 KiB
#include<bits/stdc++.h> #define DEBUG false using namespace std; int n, a, b; vector<vector<int> > g; vector<int> s; vector<int> c; bool dfs(int cur, int par){ s.push_back(cur); if(cur == b){ return true; } for(int u: g[cur]){ if(u == par) continue; if(dfs(u, cur)) return true; } s.pop_back(); return false; } int dfs2(int cur, int par){ vector<int> f; for(int u: g[cur]){ if(c[u] || u == par) continue; f.push_back(dfs2(u, cur)); } sort(f.rbegin(), f.rend()); int ans = 0; for(int i = 0; i < f.size(); i++){ ans = max(ans, f[i] + i+1); } return ans; } vector<vector<int> > h; bool sim(int v){ if(DEBUG) cout<<"SIM "<<v<<endl; int l1 = 0, l2 = 0; int r1 = h.size()-1, r2 = 0; bool pos = true; int tym = 0; while(l1 < r1){ if(l2 == h[l1].size() || h[l1][l2] + tym - (l2) + 1 <= v){ l1++; l2 = 0; }else{ if(h[l1][l2] + tym - l2 > v){ return false; } l2++; } if(r2 == h[r1].size() || h[r1][r2] + tym - (r2) + 1 <= v){ r1--; r2 = 0; }else{ if(h[r1][r2] + tym - r2 > v){ return false; } r2++; } tym++; } if(l2 == h[l1].size()) l1++; if(r2 == h[r1].size()) r1--; if(l1 == r1){ if(h[l1][max(l2, r2)] + tym - max(l2, r2) > v) return false; } return tym <= v; } signed main(){ cin>>n>>a>>b; a--, b--; g.resize(n); c.resize(n); for(int i = 0; i < n-1; i++){ int x, y; cin>>x>>y; x--, y--; g[x].push_back(y); g[y].push_back(x); } dfs(a, -1); for(int u: s){ c[u] = 1; } if(DEBUG) for(int u: s){ cout<<" S: "<<u<<endl; } for(int u: s){ if(DEBUG) cout<<"DOING "<<u<<endl; vector<int> k; for(int d: g[u]){ if(c[d]) continue; if(DEBUG) cout<<"DFS2 "<<d<<" "<<u<<endl; k.push_back(dfs2(d, u)); } sort(k.rbegin(), k.rend()); for(int i = 0; i < k.size(); i++) k[i] += i+1; for(int i = k.size()-2; i >= 0; i--){ k[i] = max(k[i], k[i+1]); } h.push_back(k); } if(DEBUG) for(vector<int> k: h){ for(int u: k){ cout<<u<<" "; } cout<<endl; } // cout<<"SIM 2: "<<sim(2)<<endl; int low = 0, high = n, mid; while(low < high){ mid = (low + high)/2; //run it with ans mid and check if its possible bool pos = sim(mid); if(pos){ high = mid; }else{ low = mid+1; } } mid = (low + high)/2; cout<<mid<<endl; }

Compilation message (stderr)

torrent.cpp: In function 'int dfs2(int, int)':
torrent.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < f.size(); i++){
                 ~~^~~~~~~~~~
torrent.cpp: In function 'bool sim(int)':
torrent.cpp:47:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(l2 == h[l1].size() || h[l1][l2] + tym - (l2) + 1 <= v){
      ~~~^~~~~~~~~~~~~~~
torrent.cpp:57:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r2 == h[r1].size() || h[r1][r2] + tym - (r2) + 1 <= v){
      ~~~^~~~~~~~~~~~~~~
torrent.cpp:67:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(l2 == h[l1].size()) l1++;
     ~~~^~~~~~~~~~~~~~~
torrent.cpp:68:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(r2 == h[r1].size()) r1--;
     ~~~^~~~~~~~~~~~~~~
torrent.cpp:44:7: warning: unused variable 'pos' [-Wunused-variable]
  bool pos = true;
       ^~~
torrent.cpp: In function 'int main()':
torrent.cpp:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < k.size(); i++) k[i] += i+1;
                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...