Submission #1226493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226493		chaeryeong	City Mapping (NOI18_citymapping)	C++20	32 / 100	1 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[]) {
	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;
	}
	for (int i = 1; i <= n; i++) {

	}
}

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