제출 #779404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779404		Sohsoh84	철로 (IOI14_rail)	C++17	30 / 100	492 ms	262144 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];
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;
		}
	}
	
	priority_queue<pair<pll, int>, vector<pair<pll, int>>, greater<pair<pll, int>>> pq;
	for (int i = 1; i < n; i++) pq.push({{D[0][i], i}, 0});
	vis[0] = true;

	for (int i = 1; i < n; i++) {
		while (vis[pq.top().X.Y]) pq.pop();
		auto [e, p] = pq.top();
		auto [d, v] = e;

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

		for (int i = 0; i < n; i++)
			pq.push({{D[v][i], i}, 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: 0 / 26
• Subtask 4: 0 / 44