Submission #1226499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226499		chaeryeong	City Mapping (NOI18_citymapping)	C++20	57 / 100	33 ms	584 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void find_roads(int n, int q, int A[], int B[], int W[]) {
	if (q == 500000) {
		int cnt = 0;
		vector <ll> c(n + 1, 0);
		for (int i = 1; i <= n; i++) {
			c[i] = get_distance(1, i);
		}
		int par[n + 1] = {};
		for (int i = 2; i <= n; i++) {
			par[i] = 1;
		}
		for (int i = 2; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				ll x = get_distance(i, j);
				if (c[i] + x == c[j] || c[j] + x == c[i]) {
					if (c[i] < c[j]) {
						if (par[j] == 0 || c[i] > c[par[j]]) {
							par[j] = i;
						}
					} else {
						if (par[i] == 0 || c[j] > c[par[i]]) {
							par[i] = j;
						}
					}
				}
			}
		}
		for (int i = 2; i <= n; i++) {
			assert(par[i] != 0);
			int idx = cnt++;
			A[idx] = par[i]; B[idx] = i; W[idx] = c[i] - c[par[i]];
		}
		return;
	}
	vector <int> ii(n, 0);
	vector <ll> c(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		c[i] = get_distance(1, i);
	}
	iota(ii.begin(), ii.end(), 1);
	stable_sort(ii.begin(), ii.end(), [&] (auto x, auto y) {
		return c[x] < c[y];
	});
	if (q == 12000) {
		vector <int> a[2] = {{1, ii[1]}, {1}};
		int cur = 0;
		for (int i = 2; i < n; i++) {
			if (c[ii[i - 1]] + get_distance(ii[i - 1], ii[i]) != c[ii[i]]) {
				cur ^= 1;
			}
			a[cur].push_back(ii[i]);
		}
		int cnt = 0;
		for (int j = 0; j + 1 < (int)a[0].size(); j++) {
			int idx = cnt; cnt++;
			A[idx] = a[0][j]; B[idx] = a[0][j + 1];
			W[idx] = c[a[0][j + 1]] - c[a[0][j]];
		}
		for (int j = 0; j + 1 < (int)a[1].size(); j++) {
			int idx = cnt; cnt++;
			A[idx] = a[1][j]; B[idx] = a[1][j + 1];
			W[idx] = c[a[1][j + 1]] - c[a[1][j]];
		}
		return;
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 0 / 43