Submission #779431

#	Time	Username	Problem	Language	Result	Execution time	Memory
779431		Sohsoh84	Rail (IOI14_rail)	C++17	8 / 100	246 ms	98672 KiB

rail

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define debug(x)		cerr << #x << ": " << x << endl;
#define sep			' '
#define X			first
#define Y			second

const ll MAXN = 5000 + 10;
const ll INF = 1e9 + 10;

int n, f, D[MAXN][MAXN], best[MAXN], best_par[MAXN];
bool vis[MAXN];

inline int get(int i, int j) {
	return getDistance(i, j);
}

void findLocation(int N, int first, int location[], int stype[]) {
	n = N;
	f = first;
	location[0] = f;
	stype[0] = 1;
	if (n == 1) return;
	
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			D[i][j] = D[j][i] = INF;
		}
	}

	vector<pll> vec;
	for (int i = 1; i < n; i++) {
		D[0][i] = D[i][0] = get(0, i);
		vec.push_back({D[0][i], i});
	}

	for (int i = 0; i < n - 2; i++) {
		int u = vec[i].Y;
		int v = vec[i + 1].Y;
		D[u][v] = D[v][u] = get(u, v);
	}

	for (int i = 0; i < n - 3; i++) {
		int u = vec[i].Y;
		int v = vec[i + 2].Y;
		D[u][v] = D[v][u] = get(u, v);
	}
	
	for (int i = 1; i < n; i++)
		best[i] = D[0][i], best_par[i] = 0;
	vis[0] = true;

	for (int i = 1; i < n; i++) {
		int v = -1;
		for (int u = 1; u < n; u++) {
			if (vis[u]) continue;
			if (v == -1 || best[u] < best[v])
				v = u;
		}

		int p = best_par[v];
		vis[v] = true;
		stype[v] = 3 - stype[p];
		location[v] = (stype[v] == 2 ? 1 : -1) * best[v] + location[p];

		for (int u = 0; u < n; u++) {
			if (!vis[u] && D[v][u] < best[u]) {
				best[u] = D[v][u];
				best_par[u] = v;
			}
		}
	}
/*
	for (int i = 0; i < n; i++)
		cerr << stype[i] << sep << location[i] << endl;
*/}

// mn location

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