# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
335050 | 2020-12-11T01:50:21 Z | TheEpicCowOfLife | Bridges (APIO19_bridges) | C++14 | 174 ms | 20068 KB |
#include <cstdio> #include <vector> #include <algorithm> #include <cassert> using namespace std; int n,m; struct e{ int a,b,w; }; vector<e> ev; int ua[100005]; int ncnt; int height[100005]; int sz[100005]; int f(int x){ if (ua[x] == x) return x; return ua[x] = f(ua[x]); } int cur_node[100005]; // cur_node[i] is the node that represents the group led by node i int par[100005][20]; int main(){ scanf("%d %d", &n, &m); height[0] = -1; ncnt = n; for (int i = 1; i <= n; i++){ ua[i] = i; sz[i] = 1; height[i] = 2e9; cur_node[i] = i; } for (int i = 1; i <= m; i++){ int a,b,w; scanf("%d %d %d", &a, &b, &w); ev.push_back({a,b,w}); } sort(ev.begin(),ev.end(),[](e l, e r){ return l.w > r.w; }); for (e cur : ev){ int a = cur.a; int b = cur.b; if (f(a) == f(b)) continue; int w = cur.w; int fa = cur_node[f(a)]; int fb = cur_node[f(b)]; int cn = ++ncnt; // cn is the new node we're making height[cn] = w; par[fa][0] = cn; par[fb][0] = cn; sz[cn] = sz[fa] + sz[fb]; ua[f(a)] = f(b); cur_node[f(b)] = cn; // printf("merging (%d %d) %d %d\n", fa,fb, sz[cn],height[cn]); } for (int i = 1; i <= 18; i++){ for (int j = 1; j <= ncnt; j++){ par[j][i] = par[par[j][i-1]][i-1]; } } int q; scanf("%d", &q); for (int i = 1; i <= q; i++){ int t,x,w; scanf("%d %d %d", &t, &x, &w); assert(t == 2); for (int i = 18; i >= 0; i--){ if (height[par[x][i]] >= w){ x = par[x][i]; } } // printf("%d\n", x); printf("%d\n", sz[x]); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 492 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 56 ms | 20068 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 37 ms | 13484 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 167 ms | 11012 KB | Output is correct |
2 | Correct | 55 ms | 1900 KB | Output is correct |
3 | Correct | 48 ms | 3552 KB | Output is correct |
4 | Correct | 44 ms | 3836 KB | Output is correct |
5 | Correct | 161 ms | 13408 KB | Output is correct |
6 | Correct | 174 ms | 14792 KB | Output is correct |
7 | Correct | 143 ms | 13408 KB | Output is correct |
8 | Correct | 122 ms | 12900 KB | Output is correct |
9 | Correct | 124 ms | 13116 KB | Output is correct |
10 | Correct | 117 ms | 12900 KB | Output is correct |
11 | Correct | 144 ms | 13792 KB | Output is correct |
12 | Correct | 150 ms | 13904 KB | Output is correct |
13 | Correct | 133 ms | 14048 KB | Output is correct |
14 | Correct | 135 ms | 13408 KB | Output is correct |
15 | Correct | 136 ms | 13408 KB | Output is correct |
16 | Correct | 166 ms | 14816 KB | Output is correct |
17 | Correct | 167 ms | 14816 KB | Output is correct |
18 | Correct | 154 ms | 14816 KB | Output is correct |
19 | Correct | 158 ms | 14824 KB | Output is correct |
20 | Correct | 135 ms | 14168 KB | Output is correct |
21 | Correct | 132 ms | 14048 KB | Output is correct |
22 | Correct | 140 ms | 14528 KB | Output is correct |
23 | Correct | 116 ms | 12196 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 56 ms | 20068 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 492 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |