Submission #1258367

#TimeUsernameProblemLanguageResultExecution timeMemory
1258367medmdgMigrations (IOI25_migrations)C++20
0 / 100
33 ms1244 KiB
#include "migrations.h" using namespace std; #define Z 9 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 ind=0; int p1= furthest(ind).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; if(ans.first==lans.first)v1=0; int v2=cur-ans.second; if(ans.second==lans.second||ans.first==lans.second)v2=0; lans=ans; stage=2; message=v1*(13)+v2; turnsLeft=4; } if(stage==2){ int v1=cur-ans.first; if(ans.first==lans.first)v1=0; int v2=cur-ans.second; if(ans.second==lans.second||ans.first==lans.second)v2=0; stage=3; message=v1*(5)+v2; turnsLeft=2; lans=ans; } if(stage==3){ int v1=cur-ans.first; if(ans.first==lans.first)v1=0; int v2=cur-ans.second; if(ans.second==lans.second||ans.first==lans.second)v2=0; stage=4; message=v1*(3)+v2; turnsLeft=1; lans=ans; } 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; } } int send_message(int N, int i, int Pi) { n=N; cur=i; if(i==1){ init(); } Tree[Pi].push_back(i); Tree[i].push_back(Pi); if(turnsLeft==0){ computeNext(); } 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-18;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-14;i>n-18;i--){ message*=Z; message+=S[i]; } pair<int,int> nans= make_pair(message/13,message%13); if(nans.first==0)nans.first=ans[0]; if(nans.second==0)nans.second=ans[1]; ans={nans.first,nans.second}; message=0; for(int i=n-12;i>n-14;i--){ message*=Z; message+=S[i]; } nans= make_pair(message/5,message%5); if(nans.first==0)nans.first=ans[0]; if(nans.second==0)nans.second=ans[1]; ans={nans.first,nans.second}; message=0; for(int i=n-11;i>n-12;i--){ message*=Z; message+=S[i]; } nans= make_pair(message/3,message%3); if(nans.first==0)nans.first=ans[0]; if(nans.second==0)nans.second=ans[1]; ans={nans.first,nans.second}; for(int i=n-10;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:119:1: warning: control reaches end of non-void function [-Wreturn-type]
  119 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...