Submission #1099511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099511		NoMercy	City Mapping (NOI18_citymapping)	C++14	100 / 100	10 ms	856 KiB

citymapping

#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;

typedef long long ll;

const int MAXN = 1e3 + 100;

vector<int> g[MAXN], del(MAXN, 0);
ll d[MAXN][MAXN];
vector<array<int, 2>> ans;
int sz[MAXN], mx[MAXN];
 
void dfs (int si) {
	sz[si] = 1; 
	mx[si] = 0;
	for (auto v : g[si]) {
		if (del[v]) continue;
		dfs (v);
		sz[si] += sz[v];
		if(sz[v] > sz[mx[si]]) mx[si] = v;
	}
}
 
void find_roads (int N, int Q, int A[], int B[], int W[]) {
	vector<int> v;
	for (int i = 2;i <= N;i ++) {
		v.push_back(i);
		d[1][i] = get_distance(1, i);
	}
	sort(v.begin(), v.end(), [](int i, int j){
		return d[1][i] < d[1][j];
	});
	int edg = 0;
	for (auto i : v) {
		// cout << i << "\n";
		for (int j = 0;j <= N + 1;j ++) {
			del[j] = 0;
		}
		int r = 1;
		while (true) {
			dfs(r);
			vector<int> path;
			path.push_back(r);
			while (mx[path.back()]) {
				path.push_back(mx[path.back()]);
			}
			if (path.size() == 1) {
				break;
			}
			// cout << path.back() << " " << i << "\n";
			ll x = d[1][path.back()] + d[1][i] - get_distance(path.back(), i);
			x /= 2;
			int j = 0;
			while (d[1][path[j]] != x) {
				j ++;
			}
			r = path[j]; 
			if (j + 1 < path.size()) {
				del[path[j + 1]] = 1;
			}
		}
		A[edg] = r; 
		B[edg] = i;
		W[edg ++] = d[1][i] - d[1][r];
		g[r].push_back(i);
	}
}

Compilation message (stderr)

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:59:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    if (j + 1 < path.size()) {
      |        ~~~~~~^~~~~~~~~~~~~

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