Submission #1062834

#TimeUsernameProblemLanguageResultExecution timeMemory
1062834NemanjaSo2005Rail (IOI14_rail)C++17
30 / 100
378 ms98564 KiB
#include "rail.h" #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=5005; int kesh[maxn][maxn],N,idxC,idxD,poz[maxn],tip[maxn],najb[maxn]; int dist(int a,int b){ if(a==b) return 0; if(kesh[a][b]==0){ // cout<<a<<" - "<<b<<": "; int x=getDistance(a,b); // cout<<x<<endl; kesh[a][b]=kesh[b][a]=x; } return kesh[a][b]; } void findLocation(int n, int first, int location[], int stype[]){ N=n; location[0]=first; stype[0]=1; if(N==1) return; for(int i=0;i<N;i++){ if(i==0) najb[i]=1; else najb[i]=0; for(int j=0;j<N;j++){ if(j==i) continue; if(dist(i,j)<dist(i,najb[i])) najb[i]=j; } } idxD=najb[0]; tip[idxD]=2; poz[idxD]=first+dist(0,idxD); idxC=najb[idxD]; tip[idxC]=1; poz[idxC]=poz[idxD]-dist(idxD,idxC); //for(int i=0;i<N;i++) // cout<<i<<": "<<najb[i]<<endl; for(int i=1;i<N;i++){ if(i==idxC or i==idxD) continue; if(najb[i]==idxC){ tip[i]=2; poz[i]=poz[idxC]+dist(i,idxC); continue; } if(najb[i]==idxD){ tip[i]=1; poz[i]=poz[idxD]-dist(i,idxD); continue; } int dc=dist(i,idxC); int dd=dist(i,idxD); int dn=min(dist(najb[i],idxC),dist(najb[i],idxD)); //cout<<i<<" "<<dc<<" "<<dd<<" "<<dn<<endl; if(dd<dc){ if(dn<dd){ tip[i]=2; poz[i]=poz[idxD]-dn+dist(najb[i],i); } else{ tip[i]=1; poz[i]=poz[idxD]-dd; } } else{ if(dn<dc){ tip[i]=1; poz[i]=poz[idxC]+dn-dist(najb[i],i); } else{ tip[i]=2; poz[i]=poz[idxC]+dc; } } } for(int i=1;i<N;i++){ location[i]=poz[i]; stype[i]=tip[i]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...