Submission #1264390

#TimeUsernameProblemLanguageResultExecution timeMemory
1264390StefanSebezMigrations (IOI25_migrations)C++20
30 / 100
33 ms1696 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,K=27; vector<int>E[N]; int par[N+50][lg+2],depth[N+50]; 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 dist[N]; void DFS(int u,int p=-1){ if(p==-1) dist[u]=0; else dist[u]=dist[p]+1; for(auto i:E[u]) if(i!=p) DFS(i,u); } int Dist1(int u,int v){ DFS(u); return dist[v]; }*/ int U,V,num[2]; int send_message(int n,int i,int Pi){ //printf(" %i %i\n",i,Pi); i++,Pi++; if(i==2){ depth[1]=1; U=V=1; num[0]=num[1]=0; for(int j=0;j<=lg;j++) par[1][j]=0; } E[i].pb(Pi);E[Pi].pb(i); 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(i,V)) U=i; else if(Dist(U,V)<Dist(U,i)) V=i; //printf("%i: %i %i\n",i-1,U-1,V-1); //printf(" * %i %i\n",num[0],num[1]); //printf("%i %i: %i %i\n",i,Pi,U,V); if(i<=n-K) return 0; if(num[0]<lg&&num[1]<lg){ if(i==U){ num[0]=lg; int bit=V>>num[1]&1; num[1]++; return 3-bit; } if(i==V){ num[1]=lg; return 4; } if(num[0]<lg){ int bit=U>>num[0]&1; num[0]++; return 1-bit; } /*if(num[1]<lg){ int bit=V>>num[1]&1; num[1]++; return bit+1; }*/ } else if(num[0]<lg&&num[1]>=lg){ if(i==U){ num[0]=lg; return 0; } if(i==V){ num[1]=lg; int bit=U>>num[0]&1; num[0]++; return 4-bit; } if(num[0]<lg){ int bit=U>>num[0]&1; num[0]++; return bit+1; } /*if(num[1]<lg){ int bit=V>>num[1]&1; num[1]++; return bit+1; }*/ } else if(num[0]>=lg&&num[1]<lg){ if(i==U){ num[0]=lg; int bit=V>>num[1]&1; num[1]++; return 4-bit; } if(i==V){ num[1]=lg; return 0; } /*if(num[0]<lg){ int bit=U>>num[0]&1; num[0]++; return bit+1; }*/ if(num[1]<lg){ int bit=V>>num[1]&1; num[1]++; return bit+1; } } else{ if(i==U){ num[0]=lg; return 3; } if(i==V){ num[1]=lg; return 4; } return 0; } return 0; } pair<int,int>longest_path(vector<int>S){ int n=S.size(); int U=-1,V=-1; int num[2]={0}; for(int i=n-K;i<n;i++){ if(num[0]<lg&&num[1]<lg){ if(S[i]==3){ num[0]=lg; U=i; } else if(S[i]==2){ num[0]=lg; U=i; V+=1<<num[1]; num[1]++; } else if(S[i]==4){ num[1]=lg; V=i; } else{ if(num[0]<lg){ if(S[i]==0) U+=1<<num[0]; num[0]++; } /*else if(num[1]<lg){ if(S[i]==2) V+=1<<num[1]; num[1]++; }*/ } //printf("{%i %i}\n",U,V); } else if(num[0]<lg&&num[1]>=lg){ if(S[i]==0){ U=i; num[0]=lg; } else if(S[i]>2){ V=i; int bit=4-S[i]; if(bit) U+=1<<num[0]; num[0]++; } else{ if(S[i]==2) U+=1<<num[0]; num[0]++; } } else if(num[0]>=lg&&num[1]<lg){ if(S[i]==0){ V=i; num[1]=lg; } else if(S[i]>2){ U=i; int bit=4-S[i]; if(bit) V+=1<<num[1]; num[1]++; } else{ if(S[i]==2) V+=1<<num[1]; num[1]++; } } else{ if(S[i]==3){ U=i; num[0]=lg; } else if(S[i]==4){ V=i; num[1]=lg; } } //printf("- %i: %i %i %i %i\n",i,U,V,num[0],num[1]); } return make_pair(U,V); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...