Submission #1258453

#TimeUsernameProblemLanguageResultExecution timeMemory
1258453medmdgMigrations (IOI25_migrations)C++20
0 / 100
32 ms1244 KiB
#include "migrations.h" #include <bits/stdc++.h> using namespace std; #define Z 10 vector<vector<int>> Tree; int n; vector<int> depth; int turnsLeft; int stage; int message; void init(){ Tree.clear(); Tree.resize(n); depth.clear(); depth.resize(n); depth[0]=0; message=0; stage=0; turnsLeft=n-31; } int cur; pair<int,int> furthest(int ind,int par=-1){ pair<int,int> ans= make_pair(0,ind); for(auto x:Tree[ind]){ if(x==par)continue; pair<int,int> tmp= furthest(x,ind); if(tmp.first>ans.first){ ans=tmp; } } ans.first++; return ans; } pair<int,int> diam(){ int p1= furthest(0).second; int p2= furthest(p1).second; if(p1>p2)swap(p1,p2); return make_pair(p1,p2); } pair<int,int> lans; void computeNext(){ pair<int,int> ans=diam(); if(stage==0){ stage=1; message=ans.first*(10001)+ans.second; turnsLeft=12; lans=ans; return; } if(stage==1){ int v1=cur-ans.first; int v2=cur-ans.second; if(ans.second==lans.second){ v1=0; v2=0; }else{ if(lans.second==ans.first){ swap(v1,v2); v2=0; }else if(lans.first==ans.first){ v1=0; } } lans=ans; stage=2; message=v1*(13)+v2; turnsLeft=4; return; } if(stage==2){ int v1=cur-ans.first; int v2=cur-ans.second; if(ans.second==lans.second){ v1=0; v2=0; }else{ if(lans.second==ans.first){ swap(v1,v2); v2=0; }else if(lans.first==ans.first){ v1=0; } } stage=3; message=v1*(5)+v2; turnsLeft=2; lans=ans; return; } if(stage==3){ int v1=cur-ans.first; int v2=cur-ans.second; if(ans.second==lans.second){ v1=0; v2=0; }else{ if(lans.second==ans.first){ swap(v1,v2); v2=0; }else if(lans.first==ans.first){ v1=0; } } stage=4; message=v1*(3)+v2; turnsLeft=1; lans=ans; return; } if(stage==4){ turnsLeft=1; if(ans== make_pair(cur-1,cur)){ message=5; lans=ans; return; } if(ans.second==cur){ if(ans.first==lans.first) message=4; else message=3; lans=ans; return; } if(ans.second==cur-1){if( ans.first==lans.first)message=2; else message=1; lans=ans;return;} message=0; lans=ans; return; } } int send_message(int N, int i, int Pi) { n=N; cur=i; if(i==1){ init(); } if(stage>3) { Tree[Pi].push_back(i); Tree[i].push_back(Pi); } if(turnsLeft==0){ computeNext(); //cout<<message<<endl; } if(stage<4) { Tree[Pi].push_back(i); Tree[i].push_back(Pi); } if (turnsLeft){ turnsLeft--; int res=message%Z; message/=Z; return res; } } pair<int, int> longest_path(vector<int> S) { n=S.size(); message=0; for(int i=n-19;i>=n-30;i--){ message*=Z; message+=S[i]; } vector<int> ans={message%10001,message/10001}; if(ans[0]>ans[1])swap(ans[0],ans[1]); message=0; for(int i=n-15;i>n-19;i--){ message*=Z; message+=S[i]; } pair<int,int> nans= make_pair(message/13,message%13); if(nans.first==0)nans.first=ans[0]; else nans.first=-nans.first+n-18; if(nans.second==0)nans.second=ans[1];else nans.second=-nans.second+n-18; ans={nans.first,nans.second}; if(ans[0]>ans[1])swap(ans[0],ans[1]); message=0; for(int i=n-13;i>n-15;i--){ message*=Z; message+=S[i]; } nans= make_pair(message/5,message%5); if(nans.first==0)nans.first=ans[0]; else nans.first=-nans.first+n-14; if(nans.second==0)nans.second=ans[1];else nans.second=-nans.second+n-14; ans={nans.first,nans.second}; if(ans[0]>ans[1])swap(ans[0],ans[1]); message=0; for(int i=n-12;i>n-13;i--){ message*=Z; message+=S[i]; } nans= make_pair(message/3,message%3); if(nans.first==0)nans.first=ans[0]; else nans.first=-nans.first+n-12; if(nans.second==0)nans.second=ans[1];else nans.second=-nans.second+n-12; ans={nans.first,nans.second}; if(ans[0]>ans[1])swap(ans[0],ans[1]); for(int i=n-11;i<n;i++){ message=S[i]; if(message==5){ ans={i-1,i}; continue; } if(message==4){ ans[1]=i; continue; } if(message==3){ swap(ans[0],ans[1]); ans[1]=i; continue; } if(message==2){ ans[1]=i-1; continue; } if(message==1){ swap(ans[0],ans[1]); ans[1]=i-1; continue; } } return make_pair(ans[0],ans[1]); }

Compilation message (stderr)

migrations.cpp: In function 'int send_message(int, int, int)':
migrations.cpp:157:1: warning: control reaches end of non-void function [-Wreturn-type]
  157 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...