# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
226624 | 2020-04-24T15:09:04 Z | stefdasca | City Mapping (NOI18_citymapping) | C++14 | 21 ms | 700 KB |
#include "citymapping.h" #include <bits/stdc++.h> using namespace std; long long dist[1002]; /* long long oxy[1002][1002]; long long get_distance(int a, int b) { return oxy[a][b]; } */ bool cmp(int a, int b) { return dist[a] < dist[b]; } int rad = 1; vector<int> v[1002]; int sts[1002], nu[1002]; void dfs(int dad, int nod) { sts[nod] = 1; for(int i = 0; i < v[nod].size(); ++i) { int vecin = v[nod][i]; if(vecin == dad) continue; dfs(nod, vecin); sts[nod] += sts[vecin]; } } int bgL(int nod) { bool ok = 1; int bst = 0; for(int i = 0; i < v[nod].size(); ++i) { int vecin = v[nod][i]; if(sts[vecin] > sts[nod] || nu[vecin]) continue; ok = 0; if(sts[vecin] > sts[bst]) bst = vecin; } if(ok) return nod; return bgL(bst); } int bgg; int optnd(int nod, long long dst) { if(dist[nod] - dist[bgg] == dst) return nod; int bst = 0; for(int i = 0; i < v[nod].size(); ++i) { int vecin = v[nod][i]; if(sts[vecin] > sts[nod] || nu[vecin]) continue; if(sts[vecin] > sts[bst]) bst = vecin; } return optnd(bst, dst); } int bstson(int nod) { int bst = 0; for(int i = 0; i < v[nod].size(); ++i) { int vecin = v[nod][i]; if(sts[vecin] > sts[nod] || nu[vecin]) continue; if(sts[vecin] > sts[bst]) bst = vecin; } return bst; } int dfssz(int rt) { int ans = 1; for(int i = 0; i < v[rt].size(); ++i) { int vecin = v[rt][i]; if(sts[vecin] > sts[rt] || nu[vecin]) continue; ans += dfssz(vecin); } return ans; } pair<int, int> solve(int nod, int pzx) { int rt = 1; int lft = pzx; while(lft > 1) { int ans = bgL(rt); long long RL = abs(dist[ans] - dist[rt]); long long LX = get_distance(nod, ans); long long RX = abs(dist[nod] - dist[rt]); long long dvg = ((RL+RX) - LX) / 2; bgg = rt; int nxt = optnd(rt, dvg); //cout << "ORZ " << rt << " " << dvg << " " << nod << " " << nxt <<'\n'; //cout << bstson(nxt) << '\n'; nu[bstson(nxt)] = 1; rt = nxt; lft = dfssz(rt); //cout << rt << " " << lft << '\n'; } //cout <<"EDG " << nod << " " << dist[nod] << " " << dist[rt] << '\n'; return {rt, dist[nod] - dist[rt]}; } void find_roads(int n, int Q, int A[], int B[], int W[]) { dist[1] = 0; for(int i = 2; i <= n; ++i) dist[i] = get_distance(1, i); int nr[1002]; for(int i = 1; i <= n; ++i) nr[i] = i; sort(nr + 1, nr + n + 1, cmp); for(int i = 2; i <= n; ++i) { A[i-2] = nr[i]; if(i != 2) { pair<int, int> ans = solve(nr[i], i-1); B[i-2] = ans.first; W[i-2] = ans.second; } else { B[i-2] = 1; W[i-2] = dist[nr[i]]; } v[A[i-2]].push_back(B[i-2]); v[B[i-2]].push_back(A[i-2]); dfs(0, 1); memset(nu, 0, sizeof(nu)); } return; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 512 KB | Correct: 2678 out of 500000 queries used. |
2 | Correct | 19 ms | 640 KB | Correct: 2420 out of 500000 queries used. |
3 | Correct | 15 ms | 512 KB | Correct: 4534 out of 500000 queries used. |
4 | Correct | 15 ms | 512 KB | Correct: 5523 out of 500000 queries used. |
5 | Correct | 16 ms | 512 KB | Correct: 3383 out of 500000 queries used. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 512 KB | Correct: 2678 out of 500000 queries used. |
2 | Correct | 19 ms | 640 KB | Correct: 2420 out of 500000 queries used. |
3 | Correct | 15 ms | 512 KB | Correct: 4534 out of 500000 queries used. |
4 | Correct | 15 ms | 512 KB | Correct: 5523 out of 500000 queries used. |
5 | Correct | 16 ms | 512 KB | Correct: 3383 out of 500000 queries used. |
6 | Correct | 21 ms | 640 KB | Correct: 2009 out of 500000 queries used. |
7 | Correct | 18 ms | 640 KB | Correct: 2063 out of 500000 queries used. |
8 | Correct | 16 ms | 512 KB | Correct: 4244 out of 500000 queries used. |
9 | Correct | 15 ms | 512 KB | Correct: 5089 out of 500000 queries used. |
10 | Correct | 16 ms | 624 KB | Correct: 3054 out of 500000 queries used. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 640 KB | Correct: 2090 out of 12000 queries used. |
2 | Correct | 19 ms | 640 KB | Correct: 2318 out of 12000 queries used. |
3 | Correct | 20 ms | 640 KB | Correct: 2470 out of 12000 queries used. |
4 | Correct | 19 ms | 640 KB | Correct: 2440 out of 12000 queries used. |
5 | Correct | 19 ms | 640 KB | Correct: 2231 out of 12000 queries used. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 640 KB | Correct: 2090 out of 12000 queries used. |
2 | Correct | 19 ms | 640 KB | Correct: 2318 out of 12000 queries used. |
3 | Correct | 20 ms | 640 KB | Correct: 2470 out of 12000 queries used. |
4 | Correct | 19 ms | 640 KB | Correct: 2440 out of 12000 queries used. |
5 | Correct | 19 ms | 640 KB | Correct: 2231 out of 12000 queries used. |
6 | Correct | 20 ms | 640 KB | Correct: 2473 out of 12000 queries used. |
7 | Correct | 20 ms | 632 KB | Correct: 2382 out of 12000 queries used. |
8 | Correct | 19 ms | 640 KB | Correct: 2207 out of 12000 queries used. |
9 | Correct | 19 ms | 688 KB | Correct: 2235 out of 12000 queries used. |
10 | Correct | 20 ms | 640 KB | Correct: 2302 out of 12000 queries used. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 512 KB | Correct: 2678 out of 500000 queries used. |
2 | Correct | 19 ms | 640 KB | Correct: 2420 out of 500000 queries used. |
3 | Correct | 15 ms | 512 KB | Correct: 4534 out of 500000 queries used. |
4 | Correct | 15 ms | 512 KB | Correct: 5523 out of 500000 queries used. |
5 | Correct | 16 ms | 512 KB | Correct: 3383 out of 500000 queries used. |
6 | Correct | 21 ms | 640 KB | Correct: 2009 out of 500000 queries used. |
7 | Correct | 18 ms | 640 KB | Correct: 2063 out of 500000 queries used. |
8 | Correct | 16 ms | 512 KB | Correct: 4244 out of 500000 queries used. |
9 | Correct | 15 ms | 512 KB | Correct: 5089 out of 500000 queries used. |
10 | Correct | 16 ms | 624 KB | Correct: 3054 out of 500000 queries used. |
11 | Correct | 20 ms | 640 KB | Correct: 2090 out of 12000 queries used. |
12 | Correct | 19 ms | 640 KB | Correct: 2318 out of 12000 queries used. |
13 | Correct | 20 ms | 640 KB | Correct: 2470 out of 12000 queries used. |
14 | Correct | 19 ms | 640 KB | Correct: 2440 out of 12000 queries used. |
15 | Correct | 19 ms | 640 KB | Correct: 2231 out of 12000 queries used. |
16 | Correct | 20 ms | 640 KB | Correct: 2473 out of 12000 queries used. |
17 | Correct | 20 ms | 632 KB | Correct: 2382 out of 12000 queries used. |
18 | Correct | 19 ms | 640 KB | Correct: 2207 out of 12000 queries used. |
19 | Correct | 19 ms | 688 KB | Correct: 2235 out of 12000 queries used. |
20 | Correct | 20 ms | 640 KB | Correct: 2302 out of 12000 queries used. |
21 | Correct | 20 ms | 640 KB | Correct: 2502 out of 25000 queries used. |
22 | Correct | 18 ms | 640 KB | Correct: 2071 out of 25000 queries used. |
23 | Correct | 18 ms | 512 KB | Correct: 2285 out of 25000 queries used. |
24 | Correct | 19 ms | 640 KB | Correct: 2036 out of 25000 queries used. |
25 | Correct | 20 ms | 512 KB | Correct: 4436 out of 25000 queries used. |
26 | Correct | 17 ms | 640 KB | Correct: 4358 out of 25000 queries used. |
27 | Correct | 16 ms | 512 KB | Correct: 4307 out of 25000 queries used. |
28 | Correct | 16 ms | 512 KB | Correct: 4417 out of 25000 queries used. |
29 | Correct | 16 ms | 512 KB | Correct: 4502 out of 25000 queries used. |
30 | Correct | 18 ms | 640 KB | Correct: 4442 out of 25000 queries used. |
31 | Correct | 17 ms | 640 KB | Correct: 5151 out of 25000 queries used. |
32 | Correct | 20 ms | 640 KB | Correct: 2223 out of 25000 queries used. |
33 | Correct | 15 ms | 640 KB | Correct: 5083 out of 25000 queries used. |
34 | Correct | 18 ms | 640 KB | Correct: 5158 out of 25000 queries used. |
35 | Correct | 16 ms | 512 KB | Correct: 5100 out of 25000 queries used. |
36 | Correct | 15 ms | 640 KB | Correct: 5118 out of 25000 queries used. |
37 | Correct | 16 ms | 512 KB | Correct: 5144 out of 25000 queries used. |
38 | Correct | 16 ms | 512 KB | Correct: 5102 out of 25000 queries used. |
39 | Correct | 16 ms | 640 KB | Correct: 5135 out of 25000 queries used. |
40 | Correct | 20 ms | 512 KB | Correct: 5168 out of 25000 queries used. |
41 | Correct | 15 ms | 512 KB | Correct: 5124 out of 25000 queries used. |
42 | Correct | 15 ms | 640 KB | Correct: 5203 out of 25000 queries used. |
43 | Correct | 20 ms | 640 KB | Correct: 2087 out of 25000 queries used. |
44 | Correct | 15 ms | 640 KB | Correct: 5116 out of 25000 queries used. |
45 | Correct | 17 ms | 512 KB | Correct: 5090 out of 25000 queries used. |
46 | Correct | 16 ms | 640 KB | Correct: 5068 out of 25000 queries used. |
47 | Correct | 18 ms | 616 KB | Correct: 5179 out of 25000 queries used. |
48 | Correct | 15 ms | 640 KB | Correct: 5135 out of 25000 queries used. |
49 | Correct | 16 ms | 616 KB | Correct: 5091 out of 25000 queries used. |
50 | Correct | 16 ms | 640 KB | Correct: 5105 out of 25000 queries used. |
51 | Correct | 16 ms | 512 KB | Correct: 5099 out of 25000 queries used. |
52 | Correct | 15 ms | 640 KB | Correct: 5128 out of 25000 queries used. |
53 | Correct | 16 ms | 512 KB | Correct: 5144 out of 25000 queries used. |
54 | Correct | 18 ms | 700 KB | Correct: 2333 out of 25000 queries used. |
55 | Correct | 16 ms | 640 KB | Correct: 5196 out of 25000 queries used. |
56 | Correct | 15 ms | 512 KB | Correct: 5141 out of 25000 queries used. |
57 | Correct | 16 ms | 512 KB | Correct: 5125 out of 25000 queries used. |
58 | Correct | 16 ms | 616 KB | Correct: 5115 out of 25000 queries used. |
59 | Correct | 18 ms | 512 KB | Correct: 5104 out of 25000 queries used. |
60 | Correct | 16 ms | 640 KB | Correct: 3041 out of 25000 queries used. |
61 | Correct | 17 ms | 512 KB | Correct: 3317 out of 25000 queries used. |
62 | Correct | 15 ms | 512 KB | Correct: 2917 out of 25000 queries used. |
63 | Correct | 17 ms | 512 KB | Correct: 3317 out of 25000 queries used. |
64 | Correct | 15 ms | 640 KB | Correct: 3103 out of 25000 queries used. |
65 | Correct | 19 ms | 640 KB | Correct: 2067 out of 25000 queries used. |
66 | Correct | 16 ms | 640 KB | Correct: 3228 out of 25000 queries used. |
67 | Correct | 19 ms | 640 KB | Correct: 2018 out of 25000 queries used. |
68 | Correct | 18 ms | 560 KB | Correct: 2394 out of 25000 queries used. |
69 | Correct | 18 ms | 640 KB | Correct: 2451 out of 25000 queries used. |
70 | Correct | 18 ms | 640 KB | Correct: 2414 out of 25000 queries used. |