Submission #1264182

#TimeUsernameProblemLanguageResultExecution timeMemory
1264182StefanSebezMigrations (IOI25_migrations)C++20
0 / 100
31 ms1252 KiB
#include "migrations.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define ll long long const int N=10050,lg=14; vector<int>E[N]; int par[N][lg+1],depth[N],U=1,V=1; int num[2]; int LCA(int u,int v){ if(depth[u]<depth[v]) swap(u,v); for(int i=lg;i>=0;i--) if(depth[par[u][i]]>=depth[v]) u=par[u][i];if(u==v) return u; for(int i=lg;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];return par[u][0]; } int Dist(int u,int v){return depth[u]+depth[v]-2*depth[LCA(u,v)];} int send_message(int n,int i,int Pi){ i++,Pi++; depth[i]=depth[Pi]+1; par[i][0]=Pi; for(int j=1;j<=lg;j++) par[i][j]=par[par[i][j-1]][j-1]; if(Dist(U,V)<Dist(U,i)) V=i; if(Dist(U,V)<Dist(i,V)) U=i; if(i<=n-2*lg) return 0; if(i==U){ num[0]=lg; return 3; } if(i==V){ num[1]=lg; return 4; } if(num[0]<lg){ int bit=U>>num[0]&1; num[0]++; return bit+1; } else{ int bit=V>>num[1]&1; num[1]++; return bit+1; } return 0; } pair<int,int>longest_path(vector<int>S){ int n=S.size(); int U=0,V=0; int num[2]={0}; int ind=0; for(int i=0;i<n;i++){ if(S[i]!=0){ind=i;break;} } for(int i=ind;i<n;i++){ if(S[i]==3){ num[0]=lg; U=i; } else if(S[i]==4){ num[1]=lg; V=i; } else{ int bit=S[i]-1; if(num[0]<lg){ U+=1<<bit; num[0]++; } else if(num[1]<lg){ V+=1<<bit; num[1]++; } } } return {U,V}; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...