Submission #436741

#TimeUsernameProblemLanguageResultExecution timeMemory
436741OdaveyRail (IOI14_rail)C++17
0 / 100
466 ms98488 KiB
// // ~oisín~ C++ Template // #include <bits/stdc++.h> #include "rail.h" #define MX_N 5001 #define mp make_pair #define mod7 1000000007 #define modpi 314159 #define PI 3.141592653589793238 #define pb push_back #define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define All(a) a.begin(),a.end() #define fi first #define se second #define ll long long int #define ull unsigned long long int int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1}; int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2}; int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1}; int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1}; int dx4[4] = {+0, +0, +1, -1}; int dy4[4] = {+1, -1, +0, +0}; ll gcd(ull a, ull b){ return (a==0)?b:gcd(b%a,a); } ll lcm(ull a, ull b){ return a*(b/gcd(a,b)); } const long long INF = 1e18; using namespace std; int d[MX_N][MX_N]; void findLocation(int n, int first, int location[], int stype[]){ for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ d[i][j] = getDistance(i, j); d[j][i] = d[i][j]; } } for(int i=0;i<n;++i){ location[i] = -1; } location[0] = first; stype[0] = 1; int shortest = 1000000009; int B = -1; for(int i=1;i<n;++i){ if(d[0][i] < shortest){ B = i; shortest = d[0][i]; } } location[B] = first+d[B][0]; stype[B] = 2; shortest = 1000000009; int A = -1; for(int i=0;i<n;++i){ if(i == B){ continue; } if(d[B][i] < shortest){ A = i; shortest = d[B][i]; } } location[A] = B-d[B][A]; stype[A] = 1; vector<pair<int, int> > L, R; for(int i=0;i<n;++i){ if(i == A || i == B){ continue; } if(d[A][i] < d[B][i]){ R.pb({d[A][i], i}); }else{ L.pb({d[B][i], i}); } } sort(All(L)); sort(All(R)); for(auto& [dist, i] : L){ if(location[i] != -1){ continue; } stype[i] = 2; location[i] = location[A] + d[A][i]; for(int j=0;j<n;++j){ if(d[A][j] == d[A][i] + d[i][j]){ location[j] = location[i] - d[i][j]; stype[j] = 1; } } } for(auto& [dist, i] : R){ if(location[i] != -1){ continue; } stype[i] = 2; location[i] = location[B] - d[B][i]; for(int j=0;j<n;++j){ if(location[j] != -1){ continue; } if(d[B][j] == d[B][i] + d[i][j]){ location[j] = location[i] + d[i][j]; stype[j] = 1; } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...