oj.uz

Submission #592705

# Submission time Handle Problem Language Result Execution time Memory
592705 2022-07-09T13:39:39 Z Blagojce City Mapping (NOI18_citymapping) C++11
93.63 / 100
 9 ms 8276 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define pb push_back
#define pq priority_queue
#define all(x) begin(x), end(x)
 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
 
const int mxn = 1003;
mt19937 _rand(time(NULL));
clock_t z;
 
#include "citymapping.h"
 
ll dist[mxn][mxn];/*
ll get_distance(int x, int y){
	cout<<"? "<<x<<' '<<y<<endl;
	ll ret;
	cin >> ret;
	return ret;
}*/
ll ask(int x, int y){
	if(x != y && dist[x][y] == 0){
		dist[x][y] = dist[y][x] = get_distance(x+1, y+1);
	}
	return dist[x][y];
}
vector<int> g;
int R1, R2;
 
 
int AA[mxn], BB[mxn], WW[mxn];
int edge_id = 0;
 
void add_edge(int x, int y, int w){
	AA[edge_id] = x;
	BB[edge_id] = y;
	WW[edge_id] = w;
	edge_id ++;
}
 
 
 
 
void decompose(vector<int> v){
	int r1 = v[_rand() % (int)v.size()];
	g = v;
	
	if((int)g.size() <= 1) return;
	
	for(auto u : g){
		ask(u, r1);
	}
	int r2 = r1;
	for(auto u : g){
		if(dist[r1][u] > dist[r1][r2]){
			r2 = u;
		}
	}
	//r1 -> r2 initial diameter
	
	for(auto u : g){
		ask(u, r2);
	}
	R1 = r1;
	R2 = r2;
	
	sort(all(g), [](const int &i, const int &j){
		return dist[R1][i] < dist[R1][j];
	});
	
	vector<int> diam;
	for(auto u : g){
		if(dist[r1][u] + dist[u][r2] == dist[r1][r2]){
			diam.pb(u);
		}
	}
	
	fr(i, 1, (int)diam.size()){
		add_edge(diam[i-1], diam[i], dist[r1][diam[i]] - dist[r1][diam[i-1]]);
	}
	vector<int> sub[(int)diam.size()];
	fr(i, 0, (int)diam.size()){
		sub[i].pb(diam[i]);
	}
	
	for(auto u : g){
		if(dist[r1][u] + dist[u][r2] == dist[r1][r2]) continue;
		fr(i, 0, (int)diam.size()){
			auto d = diam[i];
			if(dist[r1][u] - dist[r2][u] == dist[r1][d] - dist[r2][d]){
				sub[i].pb(u);
				break;
			}
		}
	}
	
	fr(i, 0, (int)diam.size()){
		decompose(sub[i]);
	}
}
 
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<int> v;
	fr(i, 0, N) v.pb(i);
	/*int r1 = 0;
	fr(i, 0, N){
		ask(0, i);
		if(dist[0][i] > dist[0][r1]) r1 = i;
	}*/
	decompose(v);
	fr(i, 0, N-1){
		A[i] = AA[i] + 1;
		B[i] = BB[i] + 1;
		W[i] = WW[i];
		//cout<<A[i]<<' '<<B[i]<<' '<<W[i]<<endl;
	}
	return;
}/*
int A[100], B[100], W[100];
int main(){
	
	find_roads(5, 0, A, B, W); 
}
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5844 KB Correct: 2472 out of 500000 queries used.
2 Correct 5 ms 7316 KB Correct: 3768 out of 500000 queries used.
3 Correct 6 ms 8148 KB Correct: 6026 out of 500000 queries used.
4 Correct 6 ms 8148 KB Correct: 6801 out of 500000 queries used.
5 Correct 6 ms 8276 KB Correct: 6571 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5844 KB Correct: 2472 out of 500000 queries used.
2 Correct 5 ms 7316 KB Correct: 3768 out of 500000 queries used.
3 Correct 6 ms 8148 KB Correct: 6026 out of 500000 queries used.
4 Correct 6 ms 8148 KB Correct: 6801 out of 500000 queries used.
5 Correct 6 ms 8276 KB Correct: 6571 out of 500000 queries used.
6 Correct 4 ms 6356 KB Correct: 2305 out of 500000 queries used.
7 Correct 6 ms 8020 KB Correct: 6563 out of 500000 queries used.
8 Correct 6 ms 8148 KB Correct: 5982 out of 500000 queries used.
9 Correct 6 ms 8276 KB Correct: 7226 out of 500000 queries used.
10 Correct 6 ms 8276 KB Correct: 4380 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7636 KB Correct: 2829 out of 12000 queries used.
2 Correct 6 ms 6624 KB Correct: 2594 out of 12000 queries used.
3 Correct 5 ms 6612 KB Correct: 2874 out of 12000 queries used.
4 Correct 5 ms 7636 KB Correct: 3046 out of 12000 queries used.
5 Correct 4 ms 5844 KB Correct: 2623 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7636 KB Correct: 2829 out of 12000 queries used.
2 Correct 6 ms 6624 KB Correct: 2594 out of 12000 queries used.
3 Correct 5 ms 6612 KB Correct: 2874 out of 12000 queries used.
4 Correct 5 ms 7636 KB Correct: 3046 out of 12000 queries used.
5 Correct 4 ms 5844 KB Correct: 2623 out of 12000 queries used.
6 Correct 6 ms 8020 KB Correct: 2386 out of 12000 queries used.
7 Correct 4 ms 6484 KB Correct: 2948 out of 12000 queries used.
8 Correct 5 ms 6228 KB Correct: 2782 out of 12000 queries used.
9 Correct 5 ms 6868 KB Correct: 2344 out of 12000 queries used.
10 Correct 7 ms 8276 KB Correct: 2070 out of 12000 queries used.

Subtask #5
36.63 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5844 KB Correct: 2472 out of 500000 queries used.
2 Correct 5 ms 7316 KB Correct: 3768 out of 500000 queries used.
3 Correct 6 ms 8148 KB Correct: 6026 out of 500000 queries used.
4 Correct 6 ms 8148 KB Correct: 6801 out of 500000 queries used.
5 Correct 6 ms 8276 KB Correct: 6571 out of 500000 queries used.
6 Correct 4 ms 6356 KB Correct: 2305 out of 500000 queries used.
7 Correct 6 ms 8020 KB Correct: 6563 out of 500000 queries used.
8 Correct 6 ms 8148 KB Correct: 5982 out of 500000 queries used.
9 Correct 6 ms 8276 KB Correct: 7226 out of 500000 queries used.
10 Correct 6 ms 8276 KB Correct: 4380 out of 500000 queries used.
11 Correct 6 ms 7636 KB Correct: 2829 out of 12000 queries used.
12 Correct 6 ms 6624 KB Correct: 2594 out of 12000 queries used.
13 Correct 5 ms 6612 KB Correct: 2874 out of 12000 queries used.
14 Correct 5 ms 7636 KB Correct: 3046 out of 12000 queries used.
15 Correct 4 ms 5844 KB Correct: 2623 out of 12000 queries used.
16 Correct 6 ms 8020 KB Correct: 2386 out of 12000 queries used.
17 Correct 4 ms 6484 KB Correct: 2948 out of 12000 queries used.
18 Correct 5 ms 6228 KB Correct: 2782 out of 12000 queries used.
19 Correct 5 ms 6868 KB Correct: 2344 out of 12000 queries used.
20 Correct 7 ms 8276 KB Correct: 2070 out of 12000 queries used.
21 Correct 5 ms 7636 KB Correct: 2229 out of 25000 queries used.
22 Correct 6 ms 8020 KB Correct: 4175 out of 25000 queries used.
23 Correct 6 ms 8148 KB Correct: 5426 out of 25000 queries used.
24 Correct 6 ms 7252 KB Correct: 3132 out of 25000 queries used.
25 Correct 6 ms 8252 KB Correct: 6388 out of 25000 queries used.
26 Correct 9 ms 8148 KB Correct: 6377 out of 25000 queries used.
27 Correct 7 ms 8232 KB Correct: 6132 out of 25000 queries used.
28 Correct 8 ms 8148 KB Correct: 6402 out of 25000 queries used.
29 Correct 7 ms 8236 KB Correct: 6464 out of 25000 queries used.
30 Correct 8 ms 8148 KB Correct: 6400 out of 25000 queries used.
31 Correct 6 ms 8276 KB Correct: 6841 out of 25000 queries used.
32 Correct 5 ms 8276 KB Correct: 2327 out of 25000 queries used.
33 Correct 6 ms 8276 KB Correct: 6843 out of 25000 queries used.
34 Correct 6 ms 8276 KB Correct: 6925 out of 25000 queries used.
35 Correct 6 ms 8148 KB Correct: 6936 out of 25000 queries used.
36 Correct 7 ms 8172 KB Correct: 6936 out of 25000 queries used.
37 Correct 8 ms 8148 KB Correct: 6819 out of 25000 queries used.
38 Correct 7 ms 8276 KB Correct: 6893 out of 25000 queries used.
39 Correct 7 ms 8276 KB Correct: 6879 out of 25000 queries used.
40 Correct 7 ms 8276 KB Correct: 6929 out of 25000 queries used.
41 Correct 7 ms 8276 KB Correct: 7007 out of 25000 queries used.
42 Correct 7 ms 8148 KB Correct: 6848 out of 25000 queries used.
43 Correct 6 ms 5504 KB Correct: 2053 out of 25000 queries used.
44 Correct 6 ms 8148 KB Correct: 6755 out of 25000 queries used.
45 Correct 7 ms 8136 KB Correct: 6895 out of 25000 queries used.
46 Correct 6 ms 8148 KB Correct: 6785 out of 25000 queries used.
47 Correct 7 ms 8188 KB Correct: 6926 out of 25000 queries used.
48 Correct 6 ms 8148 KB Correct: 6886 out of 25000 queries used.
49 Correct 6 ms 8148 KB Correct: 6771 out of 25000 queries used.
50 Correct 7 ms 8276 KB Correct: 6889 out of 25000 queries used.
51 Correct 6 ms 8148 KB Correct: 6760 out of 25000 queries used.
52 Correct 6 ms 8276 KB Correct: 6847 out of 25000 queries used.
53 Correct 6 ms 8276 KB Correct: 7118 out of 25000 queries used.
54 Correct 6 ms 8148 KB Correct: 4732 out of 25000 queries used.
55 Correct 6 ms 8148 KB Correct: 6892 out of 25000 queries used.
56 Correct 6 ms 8148 KB Correct: 6777 out of 25000 queries used.
57 Correct 8 ms 8276 KB Correct: 7113 out of 25000 queries used.
58 Correct 8 ms 8140 KB Correct: 7108 out of 25000 queries used.
59 Correct 8 ms 8276 KB Correct: 6746 out of 25000 queries used.
60 Correct 7 ms 7892 KB Correct: 6235 out of 25000 queries used.
61 Correct 8 ms 7912 KB Correct: 6542 out of 25000 queries used.
62 Correct 8 ms 7884 KB Correct: 5261 out of 25000 queries used.
63 Correct 6 ms 7892 KB Correct: 6069 out of 25000 queries used.
64 Correct 6 ms 8148 KB Correct: 4195 out of 25000 queries used.
65 Correct 6 ms 8148 KB Correct: 4783 out of 25000 queries used.
66 Correct 6 ms 7464 KB Correct: 4356 out of 25000 queries used.
67 Correct 5 ms 7380 KB Correct: 3088 out of 25000 queries used.
68 Correct 5 ms 7840 KB Correct: 3904 out of 25000 queries used.
69 Correct 6 ms 8148 KB Correct: 3604 out of 25000 queries used.
70 Correct 6 ms 7812 KB Correct: 3093 out of 25000 queries used.