# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
592691 | 2022-07-09T13:24:55 Z | Blagojce | City Mapping (NOI18_citymapping) | C++11 | 9 ms | 8336 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){ 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()){ auto d = diam[i]; for(auto s : sub[i]){ dist[d][s] = dist[r1][s] - dist[r1][d]; } } fr(i, 0, (int)diam.size()){ decompose(sub[i], diam[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, _rand()%N); 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); } */
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 6996 KB | Correct: 2140 out of 500000 queries used. |
2 | Correct | 5 ms | 8148 KB | Correct: 2742 out of 500000 queries used. |
3 | Correct | 6 ms | 8148 KB | Correct: 7394 out of 500000 queries used. |
4 | Correct | 6 ms | 8276 KB | Correct: 8393 out of 500000 queries used. |
5 | Correct | 7 ms | 8020 KB | Correct: 12433 out of 500000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 6996 KB | Correct: 2140 out of 500000 queries used. |
2 | Correct | 5 ms | 8148 KB | Correct: 2742 out of 500000 queries used. |
3 | Correct | 6 ms | 8148 KB | Correct: 7394 out of 500000 queries used. |
4 | Correct | 6 ms | 8276 KB | Correct: 8393 out of 500000 queries used. |
5 | Correct | 7 ms | 8020 KB | Correct: 12433 out of 500000 queries used. |
6 | Correct | 5 ms | 7380 KB | Correct: 2072 out of 500000 queries used. |
7 | Correct | 7 ms | 7892 KB | Correct: 8657 out of 500000 queries used. |
8 | Correct | 6 ms | 8200 KB | Correct: 6854 out of 500000 queries used. |
9 | Correct | 6 ms | 8240 KB | Correct: 8402 out of 500000 queries used. |
10 | Correct | 7 ms | 8020 KB | Correct: 7094 out of 500000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 7764 KB | Correct: 2185 out of 12000 queries used. |
2 | Correct | 6 ms | 8020 KB | Correct: 2077 out of 12000 queries used. |
3 | Correct | 5 ms | 8296 KB | Correct: 2142 out of 12000 queries used. |
4 | Correct | 5 ms | 7892 KB | Correct: 2381 out of 12000 queries used. |
5 | Correct | 5 ms | 7636 KB | Correct: 2364 out of 12000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 7764 KB | Correct: 2185 out of 12000 queries used. |
2 | Correct | 6 ms | 8020 KB | Correct: 2077 out of 12000 queries used. |
3 | Correct | 5 ms | 8296 KB | Correct: 2142 out of 12000 queries used. |
4 | Correct | 5 ms | 7892 KB | Correct: 2381 out of 12000 queries used. |
5 | Correct | 5 ms | 7636 KB | Correct: 2364 out of 12000 queries used. |
6 | Correct | 5 ms | 7380 KB | Correct: 2338 out of 12000 queries used. |
7 | Correct | 5 ms | 7992 KB | Correct: 2400 out of 12000 queries used. |
8 | Correct | 5 ms | 8020 KB | Correct: 2370 out of 12000 queries used. |
9 | Correct | 5 ms | 7892 KB | Correct: 2472 out of 12000 queries used. |
10 | Correct | 6 ms | 7892 KB | Correct: 2362 out of 12000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 6996 KB | Correct: 2140 out of 500000 queries used. |
2 | Correct | 5 ms | 8148 KB | Correct: 2742 out of 500000 queries used. |
3 | Correct | 6 ms | 8148 KB | Correct: 7394 out of 500000 queries used. |
4 | Correct | 6 ms | 8276 KB | Correct: 8393 out of 500000 queries used. |
5 | Correct | 7 ms | 8020 KB | Correct: 12433 out of 500000 queries used. |
6 | Correct | 5 ms | 7380 KB | Correct: 2072 out of 500000 queries used. |
7 | Correct | 7 ms | 7892 KB | Correct: 8657 out of 500000 queries used. |
8 | Correct | 6 ms | 8200 KB | Correct: 6854 out of 500000 queries used. |
9 | Correct | 6 ms | 8240 KB | Correct: 8402 out of 500000 queries used. |
10 | Correct | 7 ms | 8020 KB | Correct: 7094 out of 500000 queries used. |
11 | Correct | 5 ms | 7764 KB | Correct: 2185 out of 12000 queries used. |
12 | Correct | 6 ms | 8020 KB | Correct: 2077 out of 12000 queries used. |
13 | Correct | 5 ms | 8296 KB | Correct: 2142 out of 12000 queries used. |
14 | Correct | 5 ms | 7892 KB | Correct: 2381 out of 12000 queries used. |
15 | Correct | 5 ms | 7636 KB | Correct: 2364 out of 12000 queries used. |
16 | Correct | 5 ms | 7380 KB | Correct: 2338 out of 12000 queries used. |
17 | Correct | 5 ms | 7992 KB | Correct: 2400 out of 12000 queries used. |
18 | Correct | 5 ms | 8020 KB | Correct: 2370 out of 12000 queries used. |
19 | Correct | 5 ms | 7892 KB | Correct: 2472 out of 12000 queries used. |
20 | Correct | 6 ms | 7892 KB | Correct: 2362 out of 12000 queries used. |
21 | Correct | 4 ms | 6740 KB | Correct: 2146 out of 25000 queries used. |
22 | Correct | 8 ms | 8276 KB | Correct: 7764 out of 25000 queries used. |
23 | Correct | 6 ms | 7552 KB | Correct: 2490 out of 25000 queries used. |
24 | Correct | 6 ms | 8148 KB | Correct: 5882 out of 25000 queries used. |
25 | Correct | 7 ms | 8276 KB | Correct: 6828 out of 25000 queries used. |
26 | Correct | 6 ms | 8276 KB | Correct: 6568 out of 25000 queries used. |
27 | Correct | 6 ms | 8200 KB | Correct: 6743 out of 25000 queries used. |
28 | Correct | 6 ms | 8148 KB | Correct: 7094 out of 25000 queries used. |
29 | Correct | 9 ms | 8276 KB | Correct: 7649 out of 25000 queries used. |
30 | Correct | 6 ms | 8276 KB | Correct: 7215 out of 25000 queries used. |
31 | Correct | 6 ms | 8336 KB | Correct: 8431 out of 25000 queries used. |
32 | Correct | 6 ms | 8148 KB | Correct: 2403 out of 25000 queries used. |
33 | Correct | 7 ms | 8264 KB | Correct: 8385 out of 25000 queries used. |
34 | Correct | 7 ms | 8276 KB | Correct: 8431 out of 25000 queries used. |
35 | Correct | 6 ms | 8276 KB | Correct: 8346 out of 25000 queries used. |
36 | Correct | 7 ms | 8148 KB | Correct: 8372 out of 25000 queries used. |
37 | Correct | 9 ms | 8256 KB | Correct: 8393 out of 25000 queries used. |
38 | Correct | 6 ms | 8204 KB | Correct: 8451 out of 25000 queries used. |
39 | Correct | 6 ms | 8312 KB | Correct: 8381 out of 25000 queries used. |
40 | Correct | 6 ms | 8276 KB | Correct: 8399 out of 25000 queries used. |
41 | Correct | 7 ms | 8276 KB | Correct: 8443 out of 25000 queries used. |
42 | Correct | 6 ms | 8276 KB | Correct: 8422 out of 25000 queries used. |
43 | Correct | 5 ms | 7764 KB | Correct: 2376 out of 25000 queries used. |
44 | Correct | 6 ms | 8148 KB | Correct: 8297 out of 25000 queries used. |
45 | Correct | 7 ms | 8240 KB | Correct: 8359 out of 25000 queries used. |
46 | Correct | 6 ms | 8148 KB | Correct: 8295 out of 25000 queries used. |
47 | Correct | 6 ms | 8276 KB | Correct: 8547 out of 25000 queries used. |
48 | Correct | 7 ms | 8276 KB | Correct: 8402 out of 25000 queries used. |
49 | Correct | 7 ms | 8276 KB | Correct: 8459 out of 25000 queries used. |
50 | Correct | 8 ms | 8244 KB | Correct: 8481 out of 25000 queries used. |
51 | Correct | 7 ms | 8276 KB | Correct: 8460 out of 25000 queries used. |
52 | Correct | 6 ms | 8276 KB | Correct: 8381 out of 25000 queries used. |
53 | Correct | 6 ms | 8276 KB | Correct: 8440 out of 25000 queries used. |
54 | Correct | 6 ms | 8276 KB | Correct: 4960 out of 25000 queries used. |
55 | Correct | 7 ms | 8292 KB | Correct: 8442 out of 25000 queries used. |
56 | Correct | 6 ms | 8288 KB | Correct: 8915 out of 25000 queries used. |
57 | Correct | 6 ms | 8276 KB | Correct: 8961 out of 25000 queries used. |
58 | Correct | 7 ms | 8208 KB | Correct: 8308 out of 25000 queries used. |
59 | Correct | 6 ms | 8276 KB | Correct: 8372 out of 25000 queries used. |
60 | Correct | 6 ms | 7764 KB | Correct: 4420 out of 25000 queries used. |
61 | Correct | 6 ms | 8276 KB | Correct: 9444 out of 25000 queries used. |
62 | Correct | 7 ms | 7908 KB | Correct: 4938 out of 25000 queries used. |
63 | Correct | 6 ms | 8020 KB | Correct: 4757 out of 25000 queries used. |
64 | Correct | 5 ms | 7892 KB | Correct: 4565 out of 25000 queries used. |
65 | Correct | 6 ms | 7892 KB | Correct: 6066 out of 25000 queries used. |
66 | Correct | 7 ms | 8164 KB | Correct: 3847 out of 25000 queries used. |
67 | Correct | 6 ms | 7908 KB | Correct: 3332 out of 25000 queries used. |
68 | Correct | 7 ms | 8192 KB | Correct: 12054 out of 25000 queries used. |
69 | Correct | 8 ms | 8276 KB | Correct: 20114 out of 25000 queries used. |
70 | Correct | 6 ms | 7764 KB | Correct: 4557 out of 25000 queries used. |