Submission #120748

#	Time	Username	Problem	Language	Result	Execution time	Memory
120748		patrikpavic2	Rail (IOI14_rail)	C++17	30 / 100	3057 ms	223260 KiB

rail

#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});
		}
	}
	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 i = 0;i < n;i++){
				if(par[i] == r)
					par[i] = par[vv.X];
			}
			g[vv.X].PB(vv.Y);
			g[vv.Y].PB(vv.X);
		}
	}
	dfs(0,0);
	for(int i = 0;i < n;i++){
		type[i] = ty[i] + 1;
		loc[i] = l[i];
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44