Submission #779415

#	Time	Username	Problem	Language	Result	Execution time	Memory
779415		Sohsoh84	Rail (IOI14_rail)	C++17	56 / 100	456 ms	98692 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;

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++) {
			int x = get(i, j);
			D[i][j] = D[j][i] = x;
		}
	}
	
	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: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44