oj.uz

Submission #277120

# Submission time Handle Problem Language Result Execution time Memory
277120 2020-08-21T03:48:45 Z tjd229 City Mapping (NOI18_citymapping) C++14
100 / 100
 18 ms 8480 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) {
	//printf("%d,%d,%lld\n",root,x,dist);
	if (edge[root].empty()) return root;

	int leaf = dfs(root);
	ll x2l = get_distance(x, leaf);
	int lca = leaf;
	while (d[root][leaf] + dist < (d[root][lca] << 1) + x2l)
		lca = p[lca];// , printf("%d", 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[]) {
	ll mx = 0;
	int root = 0;
	for (int i = 2; i <= N; ++i) {
		d[1][i] = d[i][1] = get_distance(1, i);
		if (d[1][i] > mx) {
			mx = d[1][i];
			root = i;
		}
	}
	vector<pli > v;
	for (int i = 1; i <= N; ++i) {
		if (i == root) continue;
		d[root][i] = d[i][root] = get_distance(root, i);
		v.push_back({ d[root][i],i });
	}
	sort(v.begin(), v.end());
	sz[root] = 1;
	for (auto pr : v) {
		
		int x = pr.second;
		ll dist = pr.first;
		int par = find_par(root, x, dist);
		edge[par].push_back({ x,dist - d[par][root] });
		p[x] = par; sz[x] = 1;
		while (par) {
			++sz[par];
			d[par][x] = d[x][par] = d[root][x] - d[root][par];
			par = p[par];
		}
	}
	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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8448 KB Correct: 2993 out of 500000 queries used.
2 Correct 11 ms 8320 KB Correct: 2996 out of 500000 queries used.
3 Correct 7 ms 8320 KB Correct: 5154 out of 500000 queries used.
4 Correct 8 ms 8320 KB Correct: 6245 out of 500000 queries used.
5 Correct 8 ms 8320 KB Correct: 3848 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8448 KB Correct: 2993 out of 500000 queries used.
2 Correct 11 ms 8320 KB Correct: 2996 out of 500000 queries used.
3 Correct 7 ms 8320 KB Correct: 5154 out of 500000 queries used.
4 Correct 8 ms 8320 KB Correct: 6245 out of 500000 queries used.
5 Correct 8 ms 8320 KB Correct: 3848 out of 500000 queries used.
6 Correct 16 ms 8448 KB Correct: 2984 out of 500000 queries used.
7 Correct 13 ms 8320 KB Correct: 2990 out of 500000 queries used.
8 Correct 7 ms 8320 KB Correct: 5070 out of 500000 queries used.
9 Correct 7 ms 8320 KB Correct: 5779 out of 500000 queries used.
10 Correct 8 ms 8320 KB Correct: 3888 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8448 KB Correct: 2969 out of 12000 queries used.
2 Correct 18 ms 8480 KB Correct: 2975 out of 12000 queries used.
3 Correct 16 ms 8448 KB Correct: 2996 out of 12000 queries used.
4 Correct 16 ms 8320 KB Correct: 2975 out of 12000 queries used.
5 Correct 16 ms 8320 KB Correct: 2969 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8448 KB Correct: 2969 out of 12000 queries used.
2 Correct 18 ms 8480 KB Correct: 2975 out of 12000 queries used.
3 Correct 16 ms 8448 KB Correct: 2996 out of 12000 queries used.
4 Correct 16 ms 8320 KB Correct: 2975 out of 12000 queries used.
5 Correct 16 ms 8320 KB Correct: 2969 out of 12000 queries used.
6 Correct 15 ms 8448 KB Correct: 2990 out of 12000 queries used.
7 Correct 16 ms 8400 KB Correct: 2984 out of 12000 queries used.
8 Correct 15 ms 8448 KB Correct: 2996 out of 12000 queries used.
9 Correct 17 ms 8448 KB Correct: 2987 out of 12000 queries used.
10 Correct 16 ms 8320 KB Correct: 2978 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8448 KB Correct: 2993 out of 500000 queries used.
2 Correct 11 ms 8320 KB Correct: 2996 out of 500000 queries used.
3 Correct 7 ms 8320 KB Correct: 5154 out of 500000 queries used.
4 Correct 8 ms 8320 KB Correct: 6245 out of 500000 queries used.
5 Correct 8 ms 8320 KB Correct: 3848 out of 500000 queries used.
6 Correct 16 ms 8448 KB Correct: 2984 out of 500000 queries used.
7 Correct 13 ms 8320 KB Correct: 2990 out of 500000 queries used.
8 Correct 7 ms 8320 KB Correct: 5070 out of 500000 queries used.
9 Correct 7 ms 8320 KB Correct: 5779 out of 500000 queries used.
10 Correct 8 ms 8320 KB Correct: 3888 out of 500000 queries used.
11 Correct 16 ms 8448 KB Correct: 2969 out of 12000 queries used.
12 Correct 18 ms 8480 KB Correct: 2975 out of 12000 queries used.
13 Correct 16 ms 8448 KB Correct: 2996 out of 12000 queries used.
14 Correct 16 ms 8320 KB Correct: 2975 out of 12000 queries used.
15 Correct 16 ms 8320 KB Correct: 2969 out of 12000 queries used.
16 Correct 15 ms 8448 KB Correct: 2990 out of 12000 queries used.
17 Correct 16 ms 8400 KB Correct: 2984 out of 12000 queries used.
18 Correct 15 ms 8448 KB Correct: 2996 out of 12000 queries used.
19 Correct 17 ms 8448 KB Correct: 2987 out of 12000 queries used.
20 Correct 16 ms 8320 KB Correct: 2978 out of 12000 queries used.
21 Correct 15 ms 8320 KB Correct: 2984 out of 25000 queries used.
22 Correct 13 ms 8320 KB Correct: 2993 out of 25000 queries used.
23 Correct 13 ms 8320 KB Correct: 2975 out of 25000 queries used.
24 Correct 13 ms 8320 KB Correct: 2972 out of 25000 queries used.
25 Correct 7 ms 8320 KB Correct: 4976 out of 25000 queries used.
26 Correct 7 ms 8320 KB Correct: 4879 out of 25000 queries used.
27 Correct 7 ms 8320 KB Correct: 4838 out of 25000 queries used.
28 Correct 7 ms 8320 KB Correct: 5105 out of 25000 queries used.
29 Correct 7 ms 8320 KB Correct: 5083 out of 25000 queries used.
30 Correct 7 ms 8320 KB Correct: 5094 out of 25000 queries used.
31 Correct 7 ms 8320 KB Correct: 5831 out of 25000 queries used.
32 Correct 16 ms 8448 KB Correct: 2981 out of 25000 queries used.
33 Correct 6 ms 8320 KB Correct: 5778 out of 25000 queries used.
34 Correct 6 ms 8320 KB Correct: 5844 out of 25000 queries used.
35 Correct 7 ms 8320 KB Correct: 5789 out of 25000 queries used.
36 Correct 6 ms 8320 KB Correct: 5830 out of 25000 queries used.
37 Correct 7 ms 8320 KB Correct: 5837 out of 25000 queries used.
38 Correct 7 ms 8320 KB Correct: 5864 out of 25000 queries used.
39 Correct 7 ms 8448 KB Correct: 5797 out of 25000 queries used.
40 Correct 7 ms 8320 KB Correct: 5878 out of 25000 queries used.
41 Correct 7 ms 8320 KB Correct: 5831 out of 25000 queries used.
42 Correct 7 ms 8320 KB Correct: 5837 out of 25000 queries used.
43 Correct 15 ms 8448 KB Correct: 2990 out of 25000 queries used.
44 Correct 7 ms 8320 KB Correct: 5777 out of 25000 queries used.
45 Correct 6 ms 8320 KB Correct: 5794 out of 25000 queries used.
46 Correct 6 ms 8320 KB Correct: 5757 out of 25000 queries used.
47 Correct 7 ms 8320 KB Correct: 5831 out of 25000 queries used.
48 Correct 7 ms 8320 KB Correct: 5808 out of 25000 queries used.
49 Correct 6 ms 8320 KB Correct: 5810 out of 25000 queries used.
50 Correct 7 ms 8320 KB Correct: 5809 out of 25000 queries used.
51 Correct 7 ms 8320 KB Correct: 5801 out of 25000 queries used.
52 Correct 6 ms 8320 KB Correct: 5863 out of 25000 queries used.
53 Correct 7 ms 8320 KB Correct: 5821 out of 25000 queries used.
54 Correct 12 ms 8320 KB Correct: 2996 out of 25000 queries used.
55 Correct 7 ms 8320 KB Correct: 5772 out of 25000 queries used.
56 Correct 8 ms 8320 KB Correct: 5817 out of 25000 queries used.
57 Correct 8 ms 8320 KB Correct: 5835 out of 25000 queries used.
58 Correct 8 ms 8244 KB Correct: 5810 out of 25000 queries used.
59 Correct 9 ms 8320 KB Correct: 5796 out of 25000 queries used.
60 Correct 8 ms 8320 KB Correct: 3859 out of 25000 queries used.
61 Correct 8 ms 8320 KB Correct: 3935 out of 25000 queries used.
62 Correct 8 ms 8320 KB Correct: 3932 out of 25000 queries used.
63 Correct 8 ms 8320 KB Correct: 3848 out of 25000 queries used.
64 Correct 8 ms 8320 KB Correct: 3889 out of 25000 queries used.
65 Correct 13 ms 8320 KB Correct: 2969 out of 25000 queries used.
66 Correct 8 ms 8320 KB Correct: 3903 out of 25000 queries used.
67 Correct 16 ms 8320 KB Correct: 2975 out of 25000 queries used.
68 Correct 15 ms 8320 KB Correct: 2972 out of 25000 queries used.
69 Correct 16 ms 8376 KB Correct: 2987 out of 25000 queries used.
70 Correct 15 ms 8320 KB Correct: 2978 out of 25000 queries used.