oj.uz

Submission #200634

# Submission time Handle Problem Language Result Execution time Memory
200634 2020-02-07T18:04:39 Z wilwxk City Mapping (NOI18_citymapping) C++14
92.65 / 100
 14 ms 7160 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];
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 = rng()%int(subtree[cur].size());
	x = subtree[cur][x];
	int y = x;
	for(auto vertex : subtree[cur]) if(query(x, vertex) > query(x, y)) y = vertex;
	// 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();
 
	int p = 0;
	for(int i = 0; i < line.size(); i++) {
		int vertex = line[i].second;
		ll val = line[i].first;
		if(i != 0) ans.push_back({vertex, line[i-1].second, line[i].first-line[i-1].first});
		while(p < aux.size() && aux[p].first == val) subtree[vertex].push_back(aux[p++].second);
	}
 
	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);
	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:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < line.size(); i++) {
                 ~~^~~~~~~~~~~~~
citymapping.cpp:46:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p < aux.size() && aux[p].first == val) subtree[vertex].push_back(aux[p++].second);
         ~~^~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:58: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 9 ms 5112 KB Correct: 2492 out of 500000 queries used.
2 Correct 8 ms 3576 KB Correct: 2976 out of 500000 queries used.
3 Correct 11 ms 5368 KB Correct: 6259 out of 500000 queries used.
4 Correct 10 ms 5880 KB Correct: 6859 out of 500000 queries used.
5 Correct 11 ms 6264 KB Correct: 6632 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Correct: 2492 out of 500000 queries used.
2 Correct 8 ms 3576 KB Correct: 2976 out of 500000 queries used.
3 Correct 11 ms 5368 KB Correct: 6259 out of 500000 queries used.
4 Correct 10 ms 5880 KB Correct: 6859 out of 500000 queries used.
5 Correct 11 ms 6264 KB Correct: 6632 out of 500000 queries used.
6 Correct 9 ms 5244 KB Correct: 2238 out of 500000 queries used.
7 Correct 10 ms 5752 KB Correct: 3579 out of 500000 queries used.
8 Correct 11 ms 6392 KB Correct: 6346 out of 500000 queries used.
9 Correct 11 ms 6264 KB Correct: 7164 out of 500000 queries used.
10 Correct 10 ms 5240 KB Correct: 5731 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4344 KB Correct: 1979 out of 12000 queries used.
2 Correct 9 ms 3960 KB Correct: 2897 out of 12000 queries used.
3 Correct 8 ms 3832 KB Correct: 2212 out of 12000 queries used.
4 Correct 8 ms 3832 KB Correct: 2447 out of 12000 queries used.
5 Correct 8 ms 2808 KB Correct: 2256 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4344 KB Correct: 1979 out of 12000 queries used.
2 Correct 9 ms 3960 KB Correct: 2897 out of 12000 queries used.
3 Correct 8 ms 3832 KB Correct: 2212 out of 12000 queries used.
4 Correct 8 ms 3832 KB Correct: 2447 out of 12000 queries used.
5 Correct 8 ms 2808 KB Correct: 2256 out of 12000 queries used.
6 Correct 8 ms 3576 KB Correct: 2265 out of 12000 queries used.
7 Correct 9 ms 4472 KB Correct: 2344 out of 12000 queries used.
8 Correct 8 ms 2808 KB Correct: 2437 out of 12000 queries used.
9 Correct 10 ms 6648 KB Correct: 2766 out of 12000 queries used.
10 Correct 9 ms 4216 KB Correct: 2432 out of 12000 queries used.

Subtask #5
35.65 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Correct: 2492 out of 500000 queries used.
2 Correct 8 ms 3576 KB Correct: 2976 out of 500000 queries used.
3 Correct 11 ms 5368 KB Correct: 6259 out of 500000 queries used.
4 Correct 10 ms 5880 KB Correct: 6859 out of 500000 queries used.
5 Correct 11 ms 6264 KB Correct: 6632 out of 500000 queries used.
6 Correct 9 ms 5244 KB Correct: 2238 out of 500000 queries used.
7 Correct 10 ms 5752 KB Correct: 3579 out of 500000 queries used.
8 Correct 11 ms 6392 KB Correct: 6346 out of 500000 queries used.
9 Correct 11 ms 6264 KB Correct: 7164 out of 500000 queries used.
10 Correct 10 ms 5240 KB Correct: 5731 out of 500000 queries used.
11 Correct 8 ms 4344 KB Correct: 1979 out of 12000 queries used.
12 Correct 9 ms 3960 KB Correct: 2897 out of 12000 queries used.
13 Correct 8 ms 3832 KB Correct: 2212 out of 12000 queries used.
14 Correct 8 ms 3832 KB Correct: 2447 out of 12000 queries used.
15 Correct 8 ms 2808 KB Correct: 2256 out of 12000 queries used.
16 Correct 8 ms 3576 KB Correct: 2265 out of 12000 queries used.
17 Correct 9 ms 4472 KB Correct: 2344 out of 12000 queries used.
18 Correct 8 ms 2808 KB Correct: 2437 out of 12000 queries used.
19 Correct 10 ms 6648 KB Correct: 2766 out of 12000 queries used.
20 Correct 9 ms 4216 KB Correct: 2432 out of 12000 queries used.
21 Correct 8 ms 2936 KB Correct: 2853 out of 25000 queries used.
22 Correct 10 ms 5880 KB Correct: 6949 out of 25000 queries used.
23 Correct 12 ms 5624 KB Correct: 6162 out of 25000 queries used.
24 Correct 11 ms 6776 KB Correct: 5636 out of 25000 queries used.
25 Correct 11 ms 7160 KB Correct: 6651 out of 25000 queries used.
26 Correct 10 ms 5880 KB Correct: 6536 out of 25000 queries used.
27 Correct 10 ms 6268 KB Correct: 6388 out of 25000 queries used.
28 Correct 10 ms 6008 KB Correct: 6422 out of 25000 queries used.
29 Correct 11 ms 5752 KB Correct: 6751 out of 25000 queries used.
30 Correct 10 ms 5752 KB Correct: 6326 out of 25000 queries used.
31 Correct 10 ms 5880 KB Correct: 6935 out of 25000 queries used.
32 Correct 7 ms 2552 KB Correct: 2296 out of 25000 queries used.
33 Correct 11 ms 6776 KB Correct: 6847 out of 25000 queries used.
34 Correct 13 ms 6524 KB Correct: 6751 out of 25000 queries used.
35 Correct 11 ms 5880 KB Correct: 6882 out of 25000 queries used.
36 Correct 10 ms 5880 KB Correct: 6966 out of 25000 queries used.
37 Correct 11 ms 6776 KB Correct: 6935 out of 25000 queries used.
38 Correct 11 ms 6520 KB Correct: 6823 out of 25000 queries used.
39 Correct 11 ms 6136 KB Correct: 6845 out of 25000 queries used.
40 Correct 11 ms 6008 KB Correct: 6897 out of 25000 queries used.
41 Correct 10 ms 6008 KB Correct: 6828 out of 25000 queries used.
42 Correct 11 ms 6392 KB Correct: 7152 out of 25000 queries used.
43 Correct 8 ms 3960 KB Correct: 2281 out of 25000 queries used.
44 Correct 10 ms 6008 KB Correct: 6937 out of 25000 queries used.
45 Correct 11 ms 6808 KB Correct: 6803 out of 25000 queries used.
46 Correct 11 ms 6008 KB Correct: 6861 out of 25000 queries used.
47 Correct 11 ms 6264 KB Correct: 7065 out of 25000 queries used.
48 Correct 11 ms 6648 KB Correct: 6940 out of 25000 queries used.
49 Correct 11 ms 5880 KB Correct: 7163 out of 25000 queries used.
50 Correct 11 ms 6648 KB Correct: 6849 out of 25000 queries used.
51 Correct 14 ms 6264 KB Correct: 7058 out of 25000 queries used.
52 Correct 11 ms 6264 KB Correct: 6915 out of 25000 queries used.
53 Correct 11 ms 6776 KB Correct: 6868 out of 25000 queries used.
54 Correct 11 ms 6648 KB Correct: 6384 out of 25000 queries used.
55 Correct 10 ms 5752 KB Correct: 6802 out of 25000 queries used.
56 Correct 11 ms 6780 KB Correct: 6809 out of 25000 queries used.
57 Correct 11 ms 6392 KB Correct: 6947 out of 25000 queries used.
58 Correct 11 ms 6520 KB Correct: 7290 out of 25000 queries used.
59 Correct 11 ms 5880 KB Correct: 6820 out of 25000 queries used.
60 Correct 10 ms 6264 KB Correct: 4371 out of 25000 queries used.
61 Correct 10 ms 6136 KB Correct: 5392 out of 25000 queries used.
62 Correct 11 ms 6392 KB Correct: 5986 out of 25000 queries used.
63 Correct 11 ms 5368 KB Correct: 4683 out of 25000 queries used.
64 Correct 10 ms 6648 KB Correct: 7298 out of 25000 queries used.
65 Correct 10 ms 5752 KB Correct: 4499 out of 25000 queries used.
66 Correct 10 ms 4984 KB Correct: 4958 out of 25000 queries used.
67 Correct 10 ms 5624 KB Correct: 5672 out of 25000 queries used.
68 Correct 9 ms 4728 KB Correct: 5314 out of 25000 queries used.
69 Correct 10 ms 4600 KB Correct: 2868 out of 25000 queries used.
70 Correct 9 ms 4472 KB Correct: 4121 out of 25000 queries used.