Submission #200604

#	Time	Username	Problem	Language	Result	Execution time	Memory
200604		wilwxk	City Mapping (NOI18_citymapping)	C++14	25 / 100	33 ms	8828 KiB

citymapping

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

const int MAXN = 1e3+5;
ll dist[MAXN][MAXN];
vector<tuple<int, int, int> > ans;
vector<int> subtree[MAXN];
mt19937 rng(time(0));
int n;

ll query(int a, int b) {
	if(a == b) return 0;
	if(a > b) swap(a, b);
	if(dist[a][b]) return dist[a][b];
	// printf("query %d %d\n", a, b);
	return dist[a][b] = get_distance(a, b);
}

void solve(int cur) {
	if(subtree[cur].size() == 1) return;
	int x = rng()%int(subtree[cur].size());
	x = subtree[cur][x];
	// printf("solve %d >> %d\n", cur, x); for(auto vertex : subtree[cur]) printf("%d ", vertex); cout << endl;

	int mni; ll mn = 1e18;
	for(auto vertex : subtree[cur]) if(vertex != x && query(x, vertex) < mn) mn = query(x, vertex), mni = vertex;

	ans.push_back({x, mni, query(x, mni)});

	vector<int> aux = subtree[cur];
	subtree[cur].clear();
	for(auto vertex : aux) {
		if(query(vertex, x) < query(vertex, mni)) subtree[x].push_back(vertex);
		else subtree[mni].push_back(vertex);
	}

	solve(x);
	solve(mni);
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	n = N;

	for(int i = 1; i <= n; i++) subtree[n+1].push_back(i);
	solve(n+1);

	for(int i = 0; i < ans.size(); i++) tie(A[i], B[i], W[i]) = ans[i];
}

Compilation message (stderr)

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); i++) tie(A[i], B[i], W[i]) = ans[i];
                 ~~^~~~~~~~~~~~

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