Submission #1258444

#TimeUsernameProblemLanguageResultExecution timeMemory
1258444medmdgMigrations (IOI25_migrations)C++20
23 / 100
35 ms1504 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+1; if(ans.first==lans.first)v1=0; assert(v1<13); int v2=cur-ans.second+1; if(ans.second==lans.second||ans.first==lans.second)v2=0; assert(v2<13); lans=ans; stage=2; message=v1*(13)+v2; turnsLeft=4; return; } if(stage==2){ int v1=cur-ans.first+1; if(ans.first==lans.first)v1=0; assert(v1<5); int v2=cur-ans.second+1; if(ans.second==lans.second||ans.first==lans.second)v2=0; assert(v2<5); stage=3; message=v1*(5)+v2; turnsLeft=2; lans=ans; return; } if(stage==3){ int v1=cur-ans.first+1; if(ans.first==lans.first)v1=0; assert(v1<3); int v2=cur-ans.second+1; if(ans.second==lans.second||ans.first==lans.second)v2=0; assert(v2<3); 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(); } Tree[Pi].push_back(i); Tree[i].push_back(Pi); if(turnsLeft==0){ computeNext(); //cout<<message<<endl; } 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+1; if(nans.second==0)nans.second=ans[1];else nans.second=-nans.second+n-18+1; ans={nans.first,nans.second}; 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+1; if(nans.second==0)nans.second=ans[1];else nans.second=-nans.second+n-14+1; ans={nans.first,nans.second}; 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+1; if(nans.second==0)nans.second=ans[1];else nans.second=-nans.second+n-12+1; ans={nans.first,nans.second}; 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:129:1: warning: control reaches end of non-void function [-Wreturn-type]
  129 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...