oj.uz

Submission #200636

# Submission time Handle Problem Language Result Execution time Memory
200636 2020-02-07T18:07:49 Z wilwxk City Mapping (NOI18_citymapping) C++14
70.13 / 100
 14 ms 6904 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<int> subtree[MAXN];
ll further[MAXN][2];
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 = further[cur][0];
	int y = rng()%subtree[cur].size();
	while(subtree[cur][y] == x) y = rng()%subtree[cur].size();
	y = subtree[cur][y];
	// printf("solve %d >> %d %d\n", cur, x, y); for(auto vertex : subtree[cur]) printf("%d ", vertex); cout << endl;
 
	vector<pair<ll, int> > line;
	vector<pair<ll, int> > aux;
	for(int vertex : subtree[cur]) {
		ll val = query(x, vertex) + query(y, vertex) - query(x, y); val /= 2;
		if(val == 0) line.push_back({query(x, vertex), vertex});
		val = query(x, y) - query(vertex, y) + val;
		aux.push_back({val, vertex});
	}
	sort(line.begin(), line.end());
	sort(aux.begin(), aux.end());
	subtree[cur].clear();
	further[cur][0] = 0;
	further[cur][1] = -1;
 
	int p = 0;
	for(int i = 0; i < line.size(); i++) {
		int vertex = line[i].second;
		ll dx = line[i].first;
		while(p < aux.size() && aux[p].first == dx) {
			ll val = query(x, aux[p].second) - dx;
			if(val > further[vertex][1]) further[vertex][0] = aux[p].second, further[vertex][1] = val;
			subtree[vertex].push_back(aux[p++].second);
		}
		if(i != 0) ans.push_back({vertex, line[i-1].second, line[i].first-line[i-1].first});
	}
 
	for(auto item : line) solve(item.second);
}
 
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);
	further[n+1][0] = rng()%(n+1)+1;
	solve(n+1);
 
	for(int i = 0; i < ans.size(); i++) tie(A[i], B[i], W[i]) = ans[i];
}

Compilation message

citymapping.cpp: In function 'void solve(int)':
citymapping.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < line.size(); i++) {
                 ~~^~~~~~~~~~~~~
citymapping.cpp:48:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p < aux.size() && aux[p].first == dx) {
         ~~^~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:66: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 8 ms 3196 KB Correct: 2314 out of 500000 queries used.
2 Correct 9 ms 5496 KB Correct: 4754 out of 500000 queries used.
3 Correct 11 ms 5752 KB Correct: 7699 out of 500000 queries used.
4 Correct 11 ms 5880 KB Correct: 7867 out of 500000 queries used.
5 Correct 12 ms 6136 KB Correct: 6477 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3196 KB Correct: 2314 out of 500000 queries used.
2 Correct 9 ms 5496 KB Correct: 4754 out of 500000 queries used.
3 Correct 11 ms 5752 KB Correct: 7699 out of 500000 queries used.
4 Correct 11 ms 5880 KB Correct: 7867 out of 500000 queries used.
5 Correct 12 ms 6136 KB Correct: 6477 out of 500000 queries used.
6 Correct 10 ms 5368 KB Correct: 4825 out of 500000 queries used.
7 Correct 12 ms 6904 KB Correct: 6271 out of 500000 queries used.
8 Correct 12 ms 6904 KB Correct: 7743 out of 500000 queries used.
9 Correct 11 ms 6264 KB Correct: 7480 out of 500000 queries used.
10 Correct 10 ms 6136 KB Correct: 5158 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4600 KB Correct: 3854 out of 12000 queries used.
2 Correct 8 ms 2552 KB Correct: 3317 out of 12000 queries used.
3 Correct 9 ms 4856 KB Correct: 3964 out of 12000 queries used.
4 Correct 8 ms 3192 KB Correct: 4328 out of 12000 queries used.
5 Correct 10 ms 5752 KB Correct: 4996 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4600 KB Correct: 3854 out of 12000 queries used.
2 Correct 8 ms 2552 KB Correct: 3317 out of 12000 queries used.
3 Correct 9 ms 4856 KB Correct: 3964 out of 12000 queries used.
4 Correct 8 ms 3192 KB Correct: 4328 out of 12000 queries used.
5 Correct 10 ms 5752 KB Correct: 4996 out of 12000 queries used.
6 Correct 9 ms 4728 KB Correct: 2340 out of 12000 queries used.
7 Correct 9 ms 5624 KB Correct: 3282 out of 12000 queries used.
8 Correct 10 ms 4984 KB Correct: 3502 out of 12000 queries used.
9 Correct 10 ms 5880 KB Correct: 4521 out of 12000 queries used.
10 Correct 9 ms 4088 KB Correct: 5261 out of 12000 queries used.

Subtask #5
13.13 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3196 KB Correct: 2314 out of 500000 queries used.
2 Correct 9 ms 5496 KB Correct: 4754 out of 500000 queries used.
3 Correct 11 ms 5752 KB Correct: 7699 out of 500000 queries used.
4 Correct 11 ms 5880 KB Correct: 7867 out of 500000 queries used.
5 Correct 12 ms 6136 KB Correct: 6477 out of 500000 queries used.
6 Correct 10 ms 5368 KB Correct: 4825 out of 500000 queries used.
7 Correct 12 ms 6904 KB Correct: 6271 out of 500000 queries used.
8 Correct 12 ms 6904 KB Correct: 7743 out of 500000 queries used.
9 Correct 11 ms 6264 KB Correct: 7480 out of 500000 queries used.
10 Correct 10 ms 6136 KB Correct: 5158 out of 500000 queries used.
11 Correct 9 ms 4600 KB Correct: 3854 out of 12000 queries used.
12 Correct 8 ms 2552 KB Correct: 3317 out of 12000 queries used.
13 Correct 9 ms 4856 KB Correct: 3964 out of 12000 queries used.
14 Correct 8 ms 3192 KB Correct: 4328 out of 12000 queries used.
15 Correct 10 ms 5752 KB Correct: 4996 out of 12000 queries used.
16 Correct 9 ms 4728 KB Correct: 2340 out of 12000 queries used.
17 Correct 9 ms 5624 KB Correct: 3282 out of 12000 queries used.
18 Correct 10 ms 4984 KB Correct: 3502 out of 12000 queries used.
19 Correct 10 ms 5880 KB Correct: 4521 out of 12000 queries used.
20 Correct 9 ms 4088 KB Correct: 5261 out of 12000 queries used.
21 Correct 10 ms 6008 KB Correct: 4003 out of 25000 queries used.
22 Correct 10 ms 5496 KB Correct: 5105 out of 25000 queries used.
23 Correct 11 ms 5880 KB Correct: 6980 out of 25000 queries used.
24 Correct 10 ms 5880 KB Correct: 5908 out of 25000 queries used.
25 Correct 11 ms 6392 KB Correct: 7270 out of 25000 queries used.
26 Correct 10 ms 5752 KB Correct: 6767 out of 25000 queries used.
27 Correct 11 ms 6520 KB Correct: 7829 out of 25000 queries used.
28 Correct 12 ms 6520 KB Correct: 8833 out of 25000 queries used.
29 Correct 11 ms 6136 KB Correct: 7346 out of 25000 queries used.
30 Correct 11 ms 6264 KB Correct: 8424 out of 25000 queries used.
31 Correct 11 ms 6396 KB Correct: 8543 out of 25000 queries used.
32 Correct 10 ms 6392 KB Correct: 3929 out of 25000 queries used.
33 Correct 11 ms 6392 KB Correct: 8373 out of 25000 queries used.
34 Correct 12 ms 6648 KB Correct: 11427 out of 25000 queries used.
35 Correct 11 ms 6392 KB Correct: 8044 out of 25000 queries used.
36 Correct 11 ms 6904 KB Correct: 8848 out of 25000 queries used.
37 Correct 14 ms 6136 KB Correct: 7813 out of 25000 queries used.
38 Correct 12 ms 6904 KB Correct: 8923 out of 25000 queries used.
39 Correct 11 ms 6008 KB Correct: 7447 out of 25000 queries used.
40 Correct 11 ms 6136 KB Correct: 7911 out of 25000 queries used.
41 Correct 11 ms 6264 KB Correct: 8119 out of 25000 queries used.
42 Correct 11 ms 6392 KB Correct: 7554 out of 25000 queries used.
43 Correct 9 ms 5240 KB Correct: 2832 out of 25000 queries used.
44 Correct 11 ms 6648 KB Correct: 8289 out of 25000 queries used.
45 Correct 12 ms 6648 KB Correct: 8359 out of 25000 queries used.
46 Correct 11 ms 6652 KB Correct: 8295 out of 25000 queries used.
47 Correct 12 ms 6904 KB Correct: 7811 out of 25000 queries used.
48 Correct 12 ms 6904 KB Correct: 8652 out of 25000 queries used.
49 Correct 11 ms 6264 KB Correct: 7923 out of 25000 queries used.
50 Correct 11 ms 6648 KB Correct: 7739 out of 25000 queries used.
51 Correct 12 ms 6904 KB Correct: 8110 out of 25000 queries used.
52 Correct 11 ms 6904 KB Correct: 9491 out of 25000 queries used.
53 Correct 11 ms 6264 KB Correct: 8822 out of 25000 queries used.
54 Correct 9 ms 4092 KB Correct: 4874 out of 25000 queries used.
55 Correct 11 ms 6136 KB Correct: 7626 out of 25000 queries used.
56 Correct 13 ms 6776 KB Correct: 8245 out of 25000 queries used.
57 Correct 11 ms 6392 KB Correct: 9485 out of 25000 queries used.
58 Correct 12 ms 6648 KB Correct: 7828 out of 25000 queries used.
59 Correct 11 ms 6520 KB Correct: 7940 out of 25000 queries used.
60 Correct 10 ms 6008 KB Correct: 4690 out of 25000 queries used.
61 Correct 11 ms 5880 KB Correct: 7387 out of 25000 queries used.
62 Correct 10 ms 6008 KB Correct: 5978 out of 25000 queries used.
63 Correct 10 ms 6136 KB Correct: 5639 out of 25000 queries used.
64 Correct 11 ms 6520 KB Correct: 7462 out of 25000 queries used.
65 Correct 10 ms 5496 KB Correct: 4195 out of 25000 queries used.
66 Correct 12 ms 6904 KB Correct: 7090 out of 25000 queries used.
67 Correct 11 ms 6392 KB Correct: 6480 out of 25000 queries used.
68 Correct 11 ms 6776 KB Correct: 8064 out of 25000 queries used.
69 Correct 11 ms 6520 KB Correct: 6440 out of 25000 queries used.
70 Correct 10 ms 4604 KB Correct: 4295 out of 25000 queries used.