# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
789420 | 2023-07-21T11:25:07 Z | RecursiveCo | Connecting Supertrees (IOI20_supertrees) | C++14 | 197 ms | 22172 KB |
// CF template, version 3.0 #include <bits/stdc++.h> #include "supertrees.h" using namespace std; #define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0) #define getTest int t; cin >> t #define eachTest for (int _var=0;_var<t;_var++) #define get(name) int (name); cin >> (name) #define out(o) cout << (o) #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); } #define sortl(name) sort((name).begin(), (name).end()) #define rev(name) reverse((name).begin(), (name).end()) #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++) #define decision(b) if (b){out("YES");}else{out("NO");} //#define int long long vector<int> parent; vector<int> cycle; int find(int v) { if (parent[v] == v) return v; return parent[v] = find(parent[v]); } void unite(int a, int b, bool has, bool matters) { a = find(a); b = find(b); parent[a] = b; if (!matters) return; if (has || cycle[a] || cycle[b]) cycle[b] = 1; } int construct(vector<vector<int>> p) { // 96 points int n = p.size(); forto(n, i) parent.push_back(i), cycle.push_back(0); forto(n, i) { forto(n, j) { if (p[i][j]) unite(i, j, p[i][j] == 2, true); } } forto(n, i) { forto(n, j) { if (!p[i][j] && find(i) == find(j)) return 0; } } vector<pair<int, vector<int>>> comps; forto(n, i) { if (i == find(i)) { vector<int> cur; forto(n, j) { if (find(j) == i) cur.push_back(j); } comps.push_back({cycle[i], cur}); } } vector<vector<int>> B(n, vector<int>(n, 0)); for (auto comp: comps) { int len = comp.second.size(); if (!comp.first) { forto(len - 1, i) { int a = comp.second[i]; int b = comp.second[i + 1]; B[a][b] = 1; B[b][a] = 1; } } else { forto(n, i) parent[i] = i; forto(len, i) { forto(len, j) { int a = comp.second[i]; int b = comp.second[j]; if (p[a][b] == 1) unite(a, b, false, false); // same tree } } vector<vector<int>> trees; for (int num: comp.second) { if (find(num) == num) { vector<int> cur; for (int el: comp.second) { if (find(el) == num) cur.push_back(el); } trees.push_back(cur); } } bool can = true; for (vector<int> tree: trees) { for (int a: tree) { for (int b: tree) { if (p[a][b] == 2) { can = false; break; } } if (!can) break; } if (!can) break; } if (!can) return 0; for (vector<int> tree: trees) { int treelen = tree.size(); forto(treelen - 1, i) { int a = tree[i]; int b = tree[i + 1]; B[a][b] = 1; B[b][a] = 1; } } forto(trees.size(), i) { int a = trees[i][0]; int b = trees[(i + 1) % trees.size()][0]; B[a][b] = 1; B[b][a] = 1; } } } build(B); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 7 ms | 1108 KB | Output is correct |
7 | Correct | 161 ms | 22020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 7 ms | 1108 KB | Output is correct |
7 | Correct | 161 ms | 22020 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 7 ms | 1108 KB | Output is correct |
13 | Correct | 157 ms | 22068 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 4 ms | 596 KB | Output is correct |
17 | Correct | 74 ms | 8192 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 48 ms | 5708 KB | Output is correct |
21 | Correct | 161 ms | 22172 KB | Output is correct |
22 | Correct | 157 ms | 22020 KB | Output is correct |
23 | Correct | 164 ms | 22092 KB | Output is correct |
24 | Correct | 156 ms | 22016 KB | Output is correct |
25 | Correct | 64 ms | 8192 KB | Output is correct |
26 | Correct | 64 ms | 8076 KB | Output is correct |
27 | Correct | 166 ms | 21976 KB | Output is correct |
28 | Correct | 156 ms | 22056 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Incorrect | 0 ms | 212 KB | Answer gives possible 1 while actual possible 0 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 43 ms | 5724 KB | Output is correct |
5 | Correct | 159 ms | 22016 KB | Output is correct |
6 | Correct | 161 ms | 22040 KB | Output is correct |
7 | Correct | 162 ms | 22020 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 40 ms | 5764 KB | Output is correct |
10 | Correct | 177 ms | 22032 KB | Output is correct |
11 | Correct | 159 ms | 21988 KB | Output is correct |
12 | Correct | 197 ms | 22020 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 40 ms | 5664 KB | Output is correct |
17 | Correct | 176 ms | 22024 KB | Output is correct |
18 | Correct | 174 ms | 21992 KB | Output is correct |
19 | Correct | 159 ms | 22016 KB | Output is correct |
20 | Correct | 162 ms | 22100 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 7 ms | 1108 KB | Output is correct |
7 | Correct | 161 ms | 22020 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 7 ms | 1108 KB | Output is correct |
13 | Correct | 157 ms | 22068 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 4 ms | 596 KB | Output is correct |
17 | Correct | 74 ms | 8192 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 48 ms | 5708 KB | Output is correct |
21 | Correct | 161 ms | 22172 KB | Output is correct |
22 | Correct | 157 ms | 22020 KB | Output is correct |
23 | Correct | 164 ms | 22092 KB | Output is correct |
24 | Correct | 156 ms | 22016 KB | Output is correct |
25 | Correct | 64 ms | 8192 KB | Output is correct |
26 | Correct | 64 ms | 8076 KB | Output is correct |
27 | Correct | 166 ms | 21976 KB | Output is correct |
28 | Correct | 156 ms | 22056 KB | Output is correct |
29 | Correct | 0 ms | 212 KB | Output is correct |
30 | Correct | 0 ms | 212 KB | Output is correct |
31 | Correct | 1 ms | 212 KB | Output is correct |
32 | Incorrect | 0 ms | 212 KB | Answer gives possible 1 while actual possible 0 |
33 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 7 ms | 1108 KB | Output is correct |
7 | Correct | 161 ms | 22020 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 7 ms | 1108 KB | Output is correct |
13 | Correct | 157 ms | 22068 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 4 ms | 596 KB | Output is correct |
17 | Correct | 74 ms | 8192 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 48 ms | 5708 KB | Output is correct |
21 | Correct | 161 ms | 22172 KB | Output is correct |
22 | Correct | 157 ms | 22020 KB | Output is correct |
23 | Correct | 164 ms | 22092 KB | Output is correct |
24 | Correct | 156 ms | 22016 KB | Output is correct |
25 | Correct | 64 ms | 8192 KB | Output is correct |
26 | Correct | 64 ms | 8076 KB | Output is correct |
27 | Correct | 166 ms | 21976 KB | Output is correct |
28 | Correct | 156 ms | 22056 KB | Output is correct |
29 | Correct | 0 ms | 212 KB | Output is correct |
30 | Correct | 0 ms | 212 KB | Output is correct |
31 | Correct | 1 ms | 212 KB | Output is correct |
32 | Incorrect | 0 ms | 212 KB | Answer gives possible 1 while actual possible 0 |
33 | Halted | 0 ms | 0 KB | - |