# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
789482 | 2023-07-21T12:40:32 Z | RecursiveCo | Connecting Supertrees (IOI20_supertrees) | C++14 | 202 ms | 23012 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) { // 100 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] > 1, 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; bool three = false; 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 if (p[a][b] == 3) three = true; } } for (int a: comp.second) { for (int b: comp.second) { if (three && p[a][b] == 2) return 0; } } 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); } } if (trees.size() == 1) return 0; if (trees.size() == 2) return 0; if (three) return 0; bool can = true; for (vector<int> tree: trees) { for (int a: tree) { for (int b: tree) { if (p[a][b] > 1) { 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; } if (three) { int a = trees[0][0]; int b = trees[2][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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 7 ms | 1240 KB | Output is correct |
7 | Correct | 187 ms | 22880 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 7 ms | 1240 KB | Output is correct |
7 | Correct | 187 ms | 22880 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 296 KB | Output is correct |
10 | Correct | 1 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 7 ms | 1180 KB | Output is correct |
13 | Correct | 158 ms | 22964 KB | Output is correct |
14 | Correct | 0 ms | 304 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 3 ms | 596 KB | Output is correct |
17 | Correct | 73 ms | 9088 KB | Output is correct |
18 | Correct | 1 ms | 300 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 45 ms | 6256 KB | Output is correct |
21 | Correct | 167 ms | 22932 KB | Output is correct |
22 | Correct | 160 ms | 22936 KB | Output is correct |
23 | Correct | 202 ms | 22884 KB | Output is correct |
24 | Correct | 159 ms | 23012 KB | Output is correct |
25 | Correct | 68 ms | 9064 KB | Output is correct |
26 | Correct | 64 ms | 9044 KB | Output is correct |
27 | Correct | 164 ms | 22956 KB | Output is correct |
28 | Correct | 159 ms | 22952 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 304 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 7 ms | 1248 KB | Output is correct |
9 | Correct | 158 ms | 22836 KB | Output is correct |
10 | Correct | 1 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 8 ms | 1260 KB | Output is correct |
13 | Correct | 166 ms | 22828 KB | Output is correct |
14 | Correct | 1 ms | 300 KB | Output is correct |
15 | Correct | 0 ms | 300 KB | Output is correct |
16 | Correct | 3 ms | 668 KB | Output is correct |
17 | Correct | 93 ms | 8916 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 212 KB | Output is correct |
21 | Correct | 41 ms | 6264 KB | Output is correct |
22 | Correct | 160 ms | 22832 KB | Output is correct |
23 | Correct | 160 ms | 22756 KB | Output is correct |
24 | Correct | 164 ms | 22812 KB | Output is correct |
25 | Correct | 88 ms | 12948 KB | Output is correct |
26 | Correct | 64 ms | 8964 KB | Output is correct |
27 | Correct | 160 ms | 22788 KB | Output is correct |
28 | Correct | 192 ms | 22796 KB | Output is correct |
29 | Correct | 69 ms | 12936 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 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 | 40 ms | 6152 KB | Output is correct |
5 | Correct | 162 ms | 22836 KB | Output is correct |
6 | Correct | 161 ms | 22760 KB | Output is correct |
7 | Correct | 163 ms | 22772 KB | Output is correct |
8 | Correct | 0 ms | 300 KB | Output is correct |
9 | Correct | 44 ms | 6240 KB | Output is correct |
10 | Correct | 161 ms | 22776 KB | Output is correct |
11 | Correct | 167 ms | 22768 KB | Output is correct |
12 | Correct | 167 ms | 22772 KB | Output is correct |
13 | Correct | 0 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 45 ms | 6260 KB | Output is correct |
17 | Correct | 161 ms | 22792 KB | Output is correct |
18 | Correct | 160 ms | 22820 KB | Output is correct |
19 | Correct | 161 ms | 22800 KB | Output is correct |
20 | Correct | 158 ms | 22848 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 7 ms | 1240 KB | Output is correct |
7 | Correct | 187 ms | 22880 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 296 KB | Output is correct |
10 | Correct | 1 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 7 ms | 1180 KB | Output is correct |
13 | Correct | 158 ms | 22964 KB | Output is correct |
14 | Correct | 0 ms | 304 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 3 ms | 596 KB | Output is correct |
17 | Correct | 73 ms | 9088 KB | Output is correct |
18 | Correct | 1 ms | 300 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 45 ms | 6256 KB | Output is correct |
21 | Correct | 167 ms | 22932 KB | Output is correct |
22 | Correct | 160 ms | 22936 KB | Output is correct |
23 | Correct | 202 ms | 22884 KB | Output is correct |
24 | Correct | 159 ms | 23012 KB | Output is correct |
25 | Correct | 68 ms | 9064 KB | Output is correct |
26 | Correct | 64 ms | 9044 KB | Output is correct |
27 | Correct | 164 ms | 22956 KB | Output is correct |
28 | Correct | 159 ms | 22952 KB | Output is correct |
29 | Correct | 0 ms | 304 KB | Output is correct |
30 | Correct | 1 ms | 212 KB | Output is correct |
31 | Correct | 1 ms | 212 KB | Output is correct |
32 | Correct | 1 ms | 212 KB | Output is correct |
33 | Correct | 1 ms | 212 KB | Output is correct |
34 | Correct | 1 ms | 212 KB | Output is correct |
35 | Correct | 0 ms | 212 KB | Output is correct |
36 | Correct | 7 ms | 1248 KB | Output is correct |
37 | Correct | 158 ms | 22836 KB | Output is correct |
38 | Correct | 1 ms | 212 KB | Output is correct |
39 | Correct | 1 ms | 212 KB | Output is correct |
40 | Correct | 8 ms | 1260 KB | Output is correct |
41 | Correct | 166 ms | 22828 KB | Output is correct |
42 | Correct | 1 ms | 300 KB | Output is correct |
43 | Correct | 0 ms | 300 KB | Output is correct |
44 | Correct | 3 ms | 668 KB | Output is correct |
45 | Correct | 93 ms | 8916 KB | Output is correct |
46 | Correct | 0 ms | 212 KB | Output is correct |
47 | Correct | 0 ms | 212 KB | Output is correct |
48 | Correct | 1 ms | 212 KB | Output is correct |
49 | Correct | 41 ms | 6264 KB | Output is correct |
50 | Correct | 160 ms | 22832 KB | Output is correct |
51 | Correct | 160 ms | 22756 KB | Output is correct |
52 | Correct | 164 ms | 22812 KB | Output is correct |
53 | Correct | 88 ms | 12948 KB | Output is correct |
54 | Correct | 64 ms | 8964 KB | Output is correct |
55 | Correct | 160 ms | 22788 KB | Output is correct |
56 | Correct | 192 ms | 22796 KB | Output is correct |
57 | Correct | 69 ms | 12936 KB | Output is correct |
58 | Correct | 1 ms | 296 KB | Output is correct |
59 | Correct | 1 ms | 212 KB | Output is correct |
60 | Correct | 4 ms | 596 KB | Output is correct |
61 | Correct | 74 ms | 8908 KB | Output is correct |
62 | Correct | 1 ms | 212 KB | Output is correct |
63 | Correct | 1 ms | 212 KB | Output is correct |
64 | Correct | 0 ms | 212 KB | Output is correct |
65 | Correct | 40 ms | 6260 KB | Output is correct |
66 | Correct | 67 ms | 8944 KB | Output is correct |
67 | Correct | 66 ms | 8860 KB | Output is correct |
68 | Correct | 64 ms | 8976 KB | Output is correct |
69 | Correct | 67 ms | 12876 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 7 ms | 1240 KB | Output is correct |
7 | Correct | 187 ms | 22880 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 296 KB | Output is correct |
10 | Correct | 1 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 7 ms | 1180 KB | Output is correct |
13 | Correct | 158 ms | 22964 KB | Output is correct |
14 | Correct | 0 ms | 304 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 3 ms | 596 KB | Output is correct |
17 | Correct | 73 ms | 9088 KB | Output is correct |
18 | Correct | 1 ms | 300 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 45 ms | 6256 KB | Output is correct |
21 | Correct | 167 ms | 22932 KB | Output is correct |
22 | Correct | 160 ms | 22936 KB | Output is correct |
23 | Correct | 202 ms | 22884 KB | Output is correct |
24 | Correct | 159 ms | 23012 KB | Output is correct |
25 | Correct | 68 ms | 9064 KB | Output is correct |
26 | Correct | 64 ms | 9044 KB | Output is correct |
27 | Correct | 164 ms | 22956 KB | Output is correct |
28 | Correct | 159 ms | 22952 KB | Output is correct |
29 | Correct | 0 ms | 304 KB | Output is correct |
30 | Correct | 1 ms | 212 KB | Output is correct |
31 | Correct | 1 ms | 212 KB | Output is correct |
32 | Correct | 1 ms | 212 KB | Output is correct |
33 | Correct | 1 ms | 212 KB | Output is correct |
34 | Correct | 1 ms | 212 KB | Output is correct |
35 | Correct | 0 ms | 212 KB | Output is correct |
36 | Correct | 7 ms | 1248 KB | Output is correct |
37 | Correct | 158 ms | 22836 KB | Output is correct |
38 | Correct | 1 ms | 212 KB | Output is correct |
39 | Correct | 1 ms | 212 KB | Output is correct |
40 | Correct | 8 ms | 1260 KB | Output is correct |
41 | Correct | 166 ms | 22828 KB | Output is correct |
42 | Correct | 1 ms | 300 KB | Output is correct |
43 | Correct | 0 ms | 300 KB | Output is correct |
44 | Correct | 3 ms | 668 KB | Output is correct |
45 | Correct | 93 ms | 8916 KB | Output is correct |
46 | Correct | 0 ms | 212 KB | Output is correct |
47 | Correct | 0 ms | 212 KB | Output is correct |
48 | Correct | 1 ms | 212 KB | Output is correct |
49 | Correct | 41 ms | 6264 KB | Output is correct |
50 | Correct | 160 ms | 22832 KB | Output is correct |
51 | Correct | 160 ms | 22756 KB | Output is correct |
52 | Correct | 164 ms | 22812 KB | Output is correct |
53 | Correct | 88 ms | 12948 KB | Output is correct |
54 | Correct | 64 ms | 8964 KB | Output is correct |
55 | Correct | 160 ms | 22788 KB | Output is correct |
56 | Correct | 192 ms | 22796 KB | Output is correct |
57 | Correct | 69 ms | 12936 KB | Output is correct |
58 | Correct | 0 ms | 212 KB | Output is correct |
59 | Correct | 1 ms | 212 KB | Output is correct |
60 | Correct | 0 ms | 212 KB | Output is correct |
61 | Correct | 40 ms | 6152 KB | Output is correct |
62 | Correct | 162 ms | 22836 KB | Output is correct |
63 | Correct | 161 ms | 22760 KB | Output is correct |
64 | Correct | 163 ms | 22772 KB | Output is correct |
65 | Correct | 0 ms | 300 KB | Output is correct |
66 | Correct | 44 ms | 6240 KB | Output is correct |
67 | Correct | 161 ms | 22776 KB | Output is correct |
68 | Correct | 167 ms | 22768 KB | Output is correct |
69 | Correct | 167 ms | 22772 KB | Output is correct |
70 | Correct | 0 ms | 212 KB | Output is correct |
71 | Correct | 1 ms | 212 KB | Output is correct |
72 | Correct | 1 ms | 212 KB | Output is correct |
73 | Correct | 45 ms | 6260 KB | Output is correct |
74 | Correct | 161 ms | 22792 KB | Output is correct |
75 | Correct | 160 ms | 22820 KB | Output is correct |
76 | Correct | 161 ms | 22800 KB | Output is correct |
77 | Correct | 158 ms | 22848 KB | Output is correct |
78 | Correct | 1 ms | 296 KB | Output is correct |
79 | Correct | 1 ms | 212 KB | Output is correct |
80 | Correct | 4 ms | 596 KB | Output is correct |
81 | Correct | 74 ms | 8908 KB | Output is correct |
82 | Correct | 1 ms | 212 KB | Output is correct |
83 | Correct | 1 ms | 212 KB | Output is correct |
84 | Correct | 0 ms | 212 KB | Output is correct |
85 | Correct | 40 ms | 6260 KB | Output is correct |
86 | Correct | 67 ms | 8944 KB | Output is correct |
87 | Correct | 66 ms | 8860 KB | Output is correct |
88 | Correct | 64 ms | 8976 KB | Output is correct |
89 | Correct | 67 ms | 12876 KB | Output is correct |
90 | Correct | 1 ms | 212 KB | Output is correct |
91 | Correct | 0 ms | 212 KB | Output is correct |
92 | Correct | 4 ms | 596 KB | Output is correct |
93 | Correct | 73 ms | 9476 KB | Output is correct |
94 | Correct | 1 ms | 212 KB | Output is correct |
95 | Correct | 0 ms | 212 KB | Output is correct |
96 | Correct | 0 ms | 212 KB | Output is correct |
97 | Correct | 16 ms | 2772 KB | Output is correct |
98 | Correct | 66 ms | 9020 KB | Output is correct |
99 | Correct | 65 ms | 9448 KB | Output is correct |
100 | Correct | 64 ms | 9064 KB | Output is correct |
101 | Correct | 73 ms | 13600 KB | Output is correct |
102 | Correct | 76 ms | 13440 KB | Output is correct |
103 | Correct | 88 ms | 14068 KB | Output is correct |
104 | Correct | 82 ms | 14064 KB | Output is correct |
105 | Correct | 73 ms | 10096 KB | Output is correct |