Submission #200641

#	Time	Username	Problem	Language	Result	Execution time	Memory
200641		wilwxk	City Mapping (NOI18_citymapping)	C++14	100 / 100	29 ms	6136 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<pair<int, int> > g[MAXN];
int sz[MAXN];
ll depth[MAXN];
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];
	return dist[a][b] = get_distance(a, b);
}

bool cmp(pair<int, ll> a, pair<int, ll> b) {
	return sz[a.first] > sz[b.first];
}

void predfs(int cur) {
	sz[cur] = 1;
	for(auto edge : g[cur]) {
		int viz, w; tie(viz, w) = edge;
		depth[viz] = depth[cur]+w;
		predfs(viz);
		sz[cur] += sz[viz];
	}
	sort(g[cur].begin(), g[cur].end(), cmp);
}

ll dfs(int cur, int x) {
	// printf("%d %d\n", cur, x);

	for(auto edge : g[cur]) {
		int viz, w; tie(viz, w) = edge;
		ll val = dfs(viz, x);
		if(val < depth[cur]) return val;
	}

	ll val = query(1, x)+query(x, cur)-query(1, cur);
	val /= 2;
	val = query(1, x)-val;	

	if(val == depth[cur]) {
		g[cur].push_back({x, query(cur, x)});
		ans.push_back({cur, x, query(cur, x)});
		// printf("added %d %d %lld\n", cur, x, query(cur, x));
		return -1;
	}
	return val;

}

void process(int cur) {
	predfs(1);
	dfs(1, cur);

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

	vector<pair<ll, int> > aux;
	for(int i = 1; i <= n; i++) aux.push_back({query(1, i), i});
	sort(aux.begin(), aux.end());
	for(auto item : aux) if(item.second != 1) process(item.second);
 
	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:73: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: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 43 / 43