# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
120744 | patrikpavic2 | Rail (IOI14_rail) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rail.h"
#include <vector>
#include <algorithm>
using namespace std;
#define X first
#define Y second
#define PB push_back
const int N = 5055;
const int M = 1e6 + 500;
typedef pair < int, int > pii;
int dis[N][N], par[N], m, ty[N], l[N];
vector < pii > v[M];
vector < int > g[N];
void dfs(int x,int lst){
//printf("X = %d TY = %d L = %d\n", x, ty[x], l[x]);
for(int y : g[x]){
if(y == lst) continue;
ty[y] = !ty[x];
if(ty[x]) l[y] = l[x] - dis[x][y];
else l[y] = l[x] + dis[x][y];
dfs(y, x);
}
}
void findLocation(int n, int first, int loc[], int type[]){
l[0] = first;
for(int i = 0;i < n;i++){
par[i] = i;
for(int j = i + 1;j < n;j++){
dis[i][j] = getDistance(i, j);
dis[j][i] = dis[i][j];
if(dis[i][j] >= M) continue;
v[dis[i][j]].PB({i, j});
}
}
int kol = 0;
for(int i = 0;i < M;i++){
for(pii vv : v[i]){
if(par[vv.X] == par[vv.Y]) continue;
//printf("evo me %d %d\n", v[i].X, v[i].Y);
int r = par[vv.Y];
for(int j = 0;j < n;j++){
if(par[j] == r)
par[j] = par[vv.X];
}
kol++;
g[vv.X].PB(vv.Y);
g[vv.Y].PB(vv.X);
}
}
if(kol != n - 1){
printf("pusite mi kurac veliki ovakoooo\n");
return;
}
dfs(0,0);
for(int i = 0;i < n;i++){
type[i] = ty[i] + 1;
loc[i] = l[i];
}
}