Submission #883469

#	Time	Username	Problem	Language	Result	Execution time	Memory
883469		dubabuba	Rail (IOI14_rail)	C++14	0 / 100	3051 ms	262144 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 5050;
int dis[mxn][mxn];
int idx[mxn], lvl[mxn];
vector<int> adj[mxn];

void dfs(int u, int p = 0) {
	lvl[u] = lvl[p] ^ 1;
	for(int v : adj[u])
	if(v != p) {
		if(lvl[u] & 1) idx[v] = idx[u] - dis[u][v];
		else idx[v] = idx[u] + dis[u][v];
		dfs(v, u);
	}
}
void findLocation(int n, int st, int x[], int t[]) {
	for(int i = 0; i < n; i++)
	for(int j = i + 1; j < n; j++)
		dis[i][j] = dis[j][i] = getDistance(i, j);

	for(int i = 0; i < n; i++)
	for(int j = i + 1; j < n; j++)
	for(int k = 0; k < n; k++)
		if(dis[i][j] == dis[i][k] + dis[k][j]) {
			adj[i].push_back(j);
			adj[j].push_back(i);
		}

	lvl[0] = 1;
	dfs(0);
	for(int i = 0; i < n; i++) {
		t[i] = lvl[i] + 1;
		x[i] = idx[i];
	}
}

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