Submission #53337

#	Time	Username	Problem	Language	Result	Execution time	Memory
53337		KieranHorgan	Rail (IOI14_rail)	C++17	56 / 100	2805 ms	197952 KiB

rail

#pragma GCC optimize("Ofast")
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dist[5005][5005];
int get(int i, int j) {
	if(dist[i][j] != 0) return dist[i][j];
	return dist[i][j] = dist[j][i] = getDistance(i, j);
}
vector<int> xIsClosest[5005];
int negLoc[5005];
int vis[5005];
int sure[5005];

void findLocation(signed N, signed first, signed location[], signed stype[]) {
	for(int i = 0; i < N; i++)
		for(int j = 0; j < i; j++)
			get(i, j);

	vector<pair<int, int>> z;
	for(int i = 0; i < N; i++) {
		z.clear();
		for(int j = 0; j < N; j++) {
			if(i==j) continue;
			z.push_back({get(i,j), j});
		}
		sort(z.begin(), z.end());
		xIsClosest[z[0].second].push_back(i);
		xIsClosest[i].push_back(z[0].second);
		// cerr << i << "->" << z[0].second << endl;
	}


	queue<pair<int, int>> q;

	int xi = 1;
	for(int i = 2; i < N; i++)
		if(get(0,i) < get(0, xi))
			xi = i;
	int xo = 0;
	for(int i = 1; i < N; i++)
		if(i!=xi && get(i, xi) < get(xi, xo))
			xo = i;
	z.clear();
	for(int j = 0; j < N; j++)
		if(j != xo)
			z.push_back({get(xo,j), j});
	sort(z.rbegin(), z.rend());

	memset(negLoc, -1, sizeof(negLoc));
	negLoc[0]=first;

	q.push({0, 1});
	while(!q.empty()) {
		int i = q.front().first;
		int t = q.front().second;
		vis[i]=1;
		stype[i] = t;
		// cerr << i << ": " << t << " " << negLoc[i] << endl;
		q.pop();
		for(auto j: xIsClosest[i]) {
			if(vis[j]) continue;
			vis[j]=1;
			negLoc[j] = negLoc[i] + (t==1?get(i,j):-get(i,j));
			q.push({j, t+(t==1)-(t==2)});
		}
	}
	// cerr << endl;
	memset(sure, 0, sizeof(sure));
	while(!z.empty()) {
		int x = z.back().second;
		z.pop_back();
		if(vis[x]!=0) continue;
		sure[x]=1;

		if(get(x, xo) < get(x, xi)) {
			q.push({x, 2});
			negLoc[x] = negLoc[xo] + get(x, xo);
		} else {
			q.push({x, 1});
			negLoc[x] = negLoc[xi] - get(x, xi);
		}
		// cerr << endl;
		while(!q.empty()) {
			int i = q.front().first;
			int t = q.front().second;
			vis[i]=1;
			stype[i] = t;
			// cerr << i << ": " << t << " " << negLoc[i] << endl;
			q.pop();
			for(auto j: xIsClosest[i]) {
				if(vis[j]) continue;
				vis[j]=1;
				negLoc[j] = negLoc[i] + (t==1?get(i,j):-get(i,j));
				q.push({j, t+(t==1)-(t==2)});
			}
		}
		// cerr << endl;
	}

	for(int i = 0; i < N; i++) {
		// if(negLoc[i] == -1) exit(-1);
		if(!vis[i]) exit(-1);
		location[i] = negLoc[i];
		// cerr << i << ": " << stype[i] << " " << location[i];
		// if(sure[i]) cerr << " " << "sure";
		// cerr << endl;
	}
	// cerr << xo << " " << xi << endl;
	// cerr << negLoc[xo] << " " << negLoc[xi] << endl;
}

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