Submission #169499

#TimeUsernameProblemLanguageResultExecution timeMemory
169499algorithm16Torrent (COI16_torrent)C++14
0 / 100
925 ms26440 KiB
#include<iostream> #include<vector> #include<algorithm> using namespace std; vector <int> v[300005]; vector <int> v1; int cnt[2][300005]; bool sort_function1(int a,int b) { return cnt[0][a]>cnt[0][b]; } bool sort_function2(int a,int b) { return cnt[1][a]>cnt[1][b]; } int dfs(int x,int par,int c) { if(x==c) return 1; int ret=0; for(int i=0;i<v[x].size();i++) { if(v[x][i]==par) continue; if(dfs(v[x][i],x,c)) { ret+=1; v1.push_back(v[x][i]); } } return ret; } int f(int x,int par,int ind) { //cout << x << " " << ind << "\n"; int ret=1; for(int i=0;i<v[x].size();i++) { if(v[x][i]==par) continue; ret+=f(v[x][i],x,ind); } cnt[ind][x]=ret; return ret; } int eval(int x,int par,int ind) { //cout << x << "\n"; int ret=0,y=0; if(ind) sort(v[x].begin(),v[x].end(),sort_function2); else sort(v[x].begin(),v[x].end(),sort_function1); for(int i=0;i<v[x].size();i++) { if(v[x][i]==par) continue; //cout << v[x][i] << " " << cnt[ind][v[x][i]] << "\n"; ret=max(ret,eval(v[x][i],x,ind)+1+y); y+=1; } //cout << x << " " << ret << "\n"; //cout << "\n\n"; return ret; } int main() { int n,a,b,sol=0; cin >> n >> a >> b; a-=1; b-=1; for(int i=0;i<n-1;i++) { int x,y; cin >> x >> y; v[x-1].push_back(y-1); v[y-1].push_back(x-1); } f(a,-1,0); f(b,-1,1); dfs(a,-1,b); v1.push_back(a); reverse(v1.begin(),v1.end()); int lo=1,hi=v1.size()-1; /*cout << "\n"; for(int i=0;i<n;i++) { cout << i+1 << " " << cnt[1][i] << "\n"; } cout << "\n";*/ if(lo>=hi) { v[a].erase(find(v[a].begin(),v[a].end(),b)); v[b].erase(find(v[b].begin(),v[b].end(),a)); cout << max(eval(a,-1,0),eval(b,-1,1)); //cout << eval(a,-1,0) << " " << eval(b,-1,1) << "\n"; return 0; } while(lo<hi) { int mid=(lo+hi)/2; if(hi-lo==1) mid=hi; if(mid>0 && mid<v1.size()) { v[v1[mid-1]].erase(find(v[v1[mid-1]].begin(),v[v1[mid-1]].end(),v1[mid])); v[v1[mid]].erase(find(v[v1[mid]].begin(),v[v1[mid]].end(),v1[mid-1])); } //cout << mid << " " << eval(a,-1,0) << " " << eval(b,-1,1) << "\n"; if(eval(a,-1,0)>eval(b,-1,1)) { lo=mid; sol=eval(a,-1,0); } else { hi=mid-1; sol=eval(b,-1,1); } } cout << sol; return 0; }

Compilation message (stderr)

torrent.cpp: In function 'int dfs(int, int, int)':
torrent.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int f(int, int, int)':
torrent.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int eval(int, int, int)':
torrent.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(mid>0 && mid<v1.size()) {
               ~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...