oj.uz

Submission #277050

# Submission time Handle Problem Language Result Execution time Memory
277050 2020-08-21T02:04:48 Z tjd229 City Mapping (NOI18_citymapping) C++14
0 / 100
 2000 ms 4608 KB 
#include "citymapping.h"
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
using namespace std;
vector<pii > edge[1001];
int sz[1001],p[1001];
ll d[1001][1001];
int dfs(int x) {
	if (edge[x].empty()) return x;
	int mx = 0;
	int nxt= 0;
	for (auto p : edge[x]) {
		int c = p.first;
		if (mx < sz[c]) {
			nxt = c;
			mx = sz[c];
		}
	}
	return dfs(nxt);
}
int find_par(int root,int x,ll dist) {
	if (edge[root].empty()) return root;

	int leaf = dfs(root);
	ll x2l = get_distance(x, leaf);
	int lca = leaf;
	while (d[root][leaf] + d[root][x] < (d[root][lca] << 1) + x2l)
		lca = p[lca];

	if (edge[lca].size() <= 1) return lca;
	//2
	int l = edge[lca][0].first, r = edge[lca][1].first;
	if (sz[l] < sz[r]) return find_par(l, x, dist - d[root][l]);
	else return find_par(r, x, dist - d[root][r]);
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<pli > v;
	for (int i = 2; i <= N; ++i) {
		d[1][i] = d[i][1] = get_distance(1, i);
		v.push_back({ d[1][i],i });
	}
	sort(v.begin(), v.end());
	sz[1] = 1;
	for (auto pr : v) {
		int x = pr.second;
		ll dist = pr.first;
		int par = find_par(1, x, dist);
		edge[par].push_back({ x,dist - d[par][1] });
		p[x] = par;
		while (x) {
			++sz[x];
			d[p[x]][x] = d[x][p[x]] = d[1][x] - d[1][p[x]];
			x = p[x];
		}
	}
	int len = 0;
	for (int i = 1; i <= N; ++i) {
		for (auto p : edge[i]) {
			A[len] = i;
			B[len] = p.first;
			W[len] = p.second;
			++len;
		}
	}
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 4608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 4608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 4608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 4608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 4608 KB Time limit exceeded
2 Halted 0 ms 0 KB -