oj.uz

Submission #200641

# Submission time Handle Problem Language Result Execution time Memory
200641 2020-02-07T19:10:34 Z wilwxk City Mapping (NOI18_citymapping) C++14
100 / 100
 29 ms 6136 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4600 KB Correct: 2674 out of 500000 queries used.
2 Correct 22 ms 4728 KB Correct: 2916 out of 500000 queries used.
3 Correct 21 ms 4856 KB Correct: 4913 out of 500000 queries used.
4 Correct 20 ms 4984 KB Correct: 6045 out of 500000 queries used.
5 Correct 20 ms 4216 KB Correct: 3417 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4600 KB Correct: 2674 out of 500000 queries used.
2 Correct 22 ms 4728 KB Correct: 2916 out of 500000 queries used.
3 Correct 21 ms 4856 KB Correct: 4913 out of 500000 queries used.
4 Correct 20 ms 4984 KB Correct: 6045 out of 500000 queries used.
5 Correct 20 ms 4216 KB Correct: 3417 out of 500000 queries used.
6 Correct 24 ms 3960 KB Correct: 2012 out of 500000 queries used.
7 Correct 22 ms 4472 KB Correct: 2559 out of 500000 queries used.
8 Correct 24 ms 5496 KB Correct: 4632 out of 500000 queries used.
9 Correct 21 ms 6008 KB Correct: 5599 out of 500000 queries used.
10 Correct 20 ms 4728 KB Correct: 3075 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3960 KB Correct: 2090 out of 12000 queries used.
2 Correct 22 ms 4344 KB Correct: 2313 out of 12000 queries used.
3 Correct 22 ms 4472 KB Correct: 2452 out of 12000 queries used.
4 Correct 22 ms 4344 KB Correct: 2457 out of 12000 queries used.
5 Correct 29 ms 4088 KB Correct: 2231 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3960 KB Correct: 2090 out of 12000 queries used.
2 Correct 22 ms 4344 KB Correct: 2313 out of 12000 queries used.
3 Correct 22 ms 4472 KB Correct: 2452 out of 12000 queries used.
4 Correct 22 ms 4344 KB Correct: 2457 out of 12000 queries used.
5 Correct 29 ms 4088 KB Correct: 2231 out of 12000 queries used.
6 Correct 22 ms 4472 KB Correct: 2471 out of 12000 queries used.
7 Correct 23 ms 4344 KB Correct: 2380 out of 12000 queries used.
8 Correct 22 ms 4216 KB Correct: 2199 out of 12000 queries used.
9 Correct 24 ms 4220 KB Correct: 2232 out of 12000 queries used.
10 Correct 25 ms 4220 KB Correct: 2303 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4600 KB Correct: 2674 out of 500000 queries used.
2 Correct 22 ms 4728 KB Correct: 2916 out of 500000 queries used.
3 Correct 21 ms 4856 KB Correct: 4913 out of 500000 queries used.
4 Correct 20 ms 4984 KB Correct: 6045 out of 500000 queries used.
5 Correct 20 ms 4216 KB Correct: 3417 out of 500000 queries used.
6 Correct 24 ms 3960 KB Correct: 2012 out of 500000 queries used.
7 Correct 22 ms 4472 KB Correct: 2559 out of 500000 queries used.
8 Correct 24 ms 5496 KB Correct: 4632 out of 500000 queries used.
9 Correct 21 ms 6008 KB Correct: 5599 out of 500000 queries used.
10 Correct 20 ms 4728 KB Correct: 3075 out of 500000 queries used.
11 Correct 23 ms 3960 KB Correct: 2090 out of 12000 queries used.
12 Correct 22 ms 4344 KB Correct: 2313 out of 12000 queries used.
13 Correct 22 ms 4472 KB Correct: 2452 out of 12000 queries used.
14 Correct 22 ms 4344 KB Correct: 2457 out of 12000 queries used.
15 Correct 29 ms 4088 KB Correct: 2231 out of 12000 queries used.
16 Correct 22 ms 4472 KB Correct: 2471 out of 12000 queries used.
17 Correct 23 ms 4344 KB Correct: 2380 out of 12000 queries used.
18 Correct 22 ms 4216 KB Correct: 2199 out of 12000 queries used.
19 Correct 24 ms 4220 KB Correct: 2232 out of 12000 queries used.
20 Correct 25 ms 4220 KB Correct: 2303 out of 12000 queries used.
21 Correct 23 ms 4600 KB Correct: 2496 out of 25000 queries used.
22 Correct 25 ms 4344 KB Correct: 2569 out of 25000 queries used.
23 Correct 21 ms 4600 KB Correct: 2776 out of 25000 queries used.
24 Correct 23 ms 4344 KB Correct: 2529 out of 25000 queries used.
25 Correct 23 ms 6008 KB Correct: 4836 out of 25000 queries used.
26 Correct 22 ms 5624 KB Correct: 4743 out of 25000 queries used.
27 Correct 22 ms 5620 KB Correct: 4676 out of 25000 queries used.
28 Correct 23 ms 5880 KB Correct: 4792 out of 25000 queries used.
29 Correct 25 ms 5624 KB Correct: 4883 out of 25000 queries used.
30 Correct 21 ms 5752 KB Correct: 4810 out of 25000 queries used.
31 Correct 22 ms 6136 KB Correct: 5666 out of 25000 queries used.
32 Correct 22 ms 4216 KB Correct: 2224 out of 25000 queries used.
33 Correct 21 ms 6008 KB Correct: 5589 out of 25000 queries used.
34 Correct 23 ms 5624 KB Correct: 5662 out of 25000 queries used.
35 Correct 24 ms 6008 KB Correct: 5611 out of 25000 queries used.
36 Correct 22 ms 5856 KB Correct: 5637 out of 25000 queries used.
37 Correct 22 ms 5624 KB Correct: 5656 out of 25000 queries used.
38 Correct 21 ms 5880 KB Correct: 5593 out of 25000 queries used.
39 Correct 22 ms 6008 KB Correct: 5637 out of 25000 queries used.
40 Correct 22 ms 5880 KB Correct: 5674 out of 25000 queries used.
41 Correct 21 ms 6008 KB Correct: 5630 out of 25000 queries used.
42 Correct 21 ms 5752 KB Correct: 5702 out of 25000 queries used.
43 Correct 22 ms 3960 KB Correct: 2086 out of 25000 queries used.
44 Correct 22 ms 6012 KB Correct: 5618 out of 25000 queries used.
45 Correct 22 ms 5624 KB Correct: 5596 out of 25000 queries used.
46 Correct 22 ms 6136 KB Correct: 5564 out of 25000 queries used.
47 Correct 21 ms 5756 KB Correct: 5686 out of 25000 queries used.
48 Correct 21 ms 5752 KB Correct: 5646 out of 25000 queries used.
49 Correct 22 ms 5752 KB Correct: 5602 out of 25000 queries used.
50 Correct 21 ms 5880 KB Correct: 5630 out of 25000 queries used.
51 Correct 21 ms 5880 KB Correct: 5617 out of 25000 queries used.
52 Correct 22 ms 5880 KB Correct: 5632 out of 25000 queries used.
53 Correct 22 ms 5880 KB Correct: 5663 out of 25000 queries used.
54 Correct 22 ms 4216 KB Correct: 2832 out of 25000 queries used.
55 Correct 25 ms 5880 KB Correct: 5715 out of 25000 queries used.
56 Correct 22 ms 6008 KB Correct: 5633 out of 25000 queries used.
57 Correct 22 ms 6008 KB Correct: 5651 out of 25000 queries used.
58 Correct 21 ms 5752 KB Correct: 5610 out of 25000 queries used.
59 Correct 21 ms 5840 KB Correct: 5629 out of 25000 queries used.
60 Correct 19 ms 4984 KB Correct: 3065 out of 25000 queries used.
61 Correct 20 ms 4856 KB Correct: 3344 out of 25000 queries used.
62 Correct 19 ms 4344 KB Correct: 2941 out of 25000 queries used.
63 Correct 20 ms 4604 KB Correct: 3346 out of 25000 queries used.
64 Correct 20 ms 4728 KB Correct: 3132 out of 25000 queries used.
65 Correct 22 ms 3960 KB Correct: 2558 out of 25000 queries used.
66 Correct 20 ms 4856 KB Correct: 3244 out of 25000 queries used.
67 Correct 23 ms 4600 KB Correct: 2510 out of 25000 queries used.
68 Correct 22 ms 4344 KB Correct: 2890 out of 25000 queries used.
69 Correct 23 ms 4988 KB Correct: 2949 out of 25000 queries used.
70 Correct 25 ms 4344 KB Correct: 2913 out of 25000 queries used.