# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
497135 | 2021-12-22T13:55:02 Z | Hanksburger | Connecting Supertrees (IOI20_supertrees) | C++17 | 195 ms | 24064 KB |
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; vector<vector<int> > grp, ans; bool visited[1005]; vector<int> tmp; queue<int> Q; int construct(vector<vector<int> > P) { int N=P.size(); bool subtask1=1, subtask2=1, subtask3=1; for (int i=0; i<N; i++) { for (int j=i+1; j<N; j++) { if (P[i][j]==0 || P[i][j]==2 || P[i][j]==3) subtask1=0; if (P[i][j]==2 || P[i][j]==3) subtask2=0; if (P[i][j]==1 || P[i][j]==3) subtask3=0; } } if (subtask1) { tmp.push_back(0); for (int i=1; i<N; i++) tmp.push_back(1); ans.push_back(tmp); for (int i=1; i<N; i++) { tmp.clear(); tmp.push_back(1); for (int j=1; j<N; j++) tmp.push_back(0); ans.push_back(tmp); } } else if (subtask2) { for (int i=0; i<N; i++) { if (visited[i]) continue; tmp.clear(); tmp.push_back(i); Q.push(i); visited[i]=1; while (!Q.empty()) { int u=Q.front(); Q.pop(); for (int j=0; j<N; j++) { if (P[u][j] && !visited[j]) { tmp.push_back(j); Q.push(j); visited[j]=1; } } } grp.push_back(tmp); } for (int i=0; i<grp.size(); i++) { for (int j=0; j<grp[i].size(); j++) { int u=grp[i][j]; for (int k=j+1; k<grp[i].size(); k++) if (!P[u][grp[i][k]]) return 0; } } for (int i=0; i<N; i++) { tmp.clear(); for (int j=0; j<N; j++) tmp.push_back(0); ans.push_back(tmp); } for (int i=0; i<grp.size(); i++) { for (int j=1; j<grp[i].size(); j++) { int u=grp[i][j-1], v=grp[i][j]; ans[u][v]=ans[v][u]=1; } } } else { for (int i=0; i<N; i++) { if (visited[i]) continue; tmp.clear(); tmp.push_back(i); Q.push(i); visited[i]=1; while (!Q.empty()) { int u=Q.front(); Q.pop(); for (int j=0; j<N; j++) { if (P[u][j] && !visited[j]) { tmp.push_back(j); Q.push(j); visited[j]=1; } } } grp.push_back(tmp); } for (int i=0; i<grp.size(); i++) { if (grp[i].size()==2) return 0; for (int j=0; j<grp[i].size(); j++) { int u=grp[i][j]; for (int k=j+1; k<grp[i].size(); k++) if (!P[u][grp[i][k]]) return 0; } } for (int i=0; i<N; i++) { tmp.clear(); for (int j=0; j<N; j++) tmp.push_back(0); ans.push_back(tmp); } for (int i=0; i<grp.size(); i++) { for (int j=1; j<grp[i].size(); j++) { int u=grp[i][j-1], v=grp[i][j]; ans[u][v]=ans[v][u]=1; } if (grp[i].size()>=3) { int u=grp[i][0], v=grp[i][grp[i].size()-1]; ans[u][v]=ans[v][u]=1; } } } build(ans); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 7 ms | 1100 KB | Output is correct |
7 | Correct | 172 ms | 21984 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 7 ms | 1100 KB | Output is correct |
7 | Correct | 172 ms | 21984 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 8 ms | 1092 KB | Output is correct |
13 | Correct | 167 ms | 22096 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 4 ms | 568 KB | Output is correct |
17 | Correct | 78 ms | 8208 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
20 | Correct | 42 ms | 5764 KB | Output is correct |
21 | Correct | 183 ms | 22288 KB | Output is correct |
22 | Correct | 166 ms | 22156 KB | Output is correct |
23 | Correct | 176 ms | 22024 KB | Output is correct |
24 | Correct | 167 ms | 22184 KB | Output is correct |
25 | Correct | 78 ms | 8228 KB | Output is correct |
26 | Correct | 66 ms | 8268 KB | Output is correct |
27 | Correct | 185 ms | 22040 KB | Output is correct |
28 | Correct | 166 ms | 22084 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 7 ms | 1192 KB | Output is correct |
9 | Correct | 168 ms | 24064 KB | Output is correct |
10 | Correct | 1 ms | 296 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 8 ms | 1228 KB | Output is correct |
13 | Correct | 195 ms | 23904 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 296 KB | Output is correct |
16 | Correct | 3 ms | 588 KB | Output is correct |
17 | Correct | 78 ms | 10028 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 0 ms | 296 KB | Output is correct |
20 | Correct | 1 ms | 296 KB | Output is correct |
21 | Correct | 45 ms | 6260 KB | Output is correct |
22 | Correct | 169 ms | 23920 KB | Output is correct |
23 | Correct | 168 ms | 24004 KB | Output is correct |
24 | Correct | 173 ms | 23912 KB | Output is correct |
25 | Correct | 68 ms | 10180 KB | Output is correct |
26 | Correct | 68 ms | 10108 KB | Output is correct |
27 | Correct | 166 ms | 23980 KB | Output is correct |
28 | Correct | 178 ms | 23972 KB | Output is correct |
29 | Correct | 78 ms | 10180 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 296 KB | Output is correct |
4 | Correct | 48 ms | 6196 KB | Output is correct |
5 | Correct | 171 ms | 23920 KB | Output is correct |
6 | Correct | 169 ms | 24008 KB | Output is correct |
7 | Correct | 180 ms | 23956 KB | Output is correct |
8 | Correct | 0 ms | 288 KB | Output is correct |
9 | Correct | 44 ms | 6192 KB | Output is correct |
10 | Correct | 172 ms | 23936 KB | Output is correct |
11 | Correct | 168 ms | 24004 KB | Output is correct |
12 | Correct | 182 ms | 23892 KB | Output is correct |
13 | Correct | 1 ms | 204 KB | Output is correct |
14 | Incorrect | 0 ms | 204 KB | Too many ways to get from 4 to 8, should be 1 found no less than 2 |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 7 ms | 1100 KB | Output is correct |
7 | Correct | 172 ms | 21984 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 8 ms | 1092 KB | Output is correct |
13 | Correct | 167 ms | 22096 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 4 ms | 568 KB | Output is correct |
17 | Correct | 78 ms | 8208 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
20 | Correct | 42 ms | 5764 KB | Output is correct |
21 | Correct | 183 ms | 22288 KB | Output is correct |
22 | Correct | 166 ms | 22156 KB | Output is correct |
23 | Correct | 176 ms | 22024 KB | Output is correct |
24 | Correct | 167 ms | 22184 KB | Output is correct |
25 | Correct | 78 ms | 8228 KB | Output is correct |
26 | Correct | 66 ms | 8268 KB | Output is correct |
27 | Correct | 185 ms | 22040 KB | Output is correct |
28 | Correct | 166 ms | 22084 KB | Output is correct |
29 | Correct | 0 ms | 204 KB | Output is correct |
30 | Correct | 0 ms | 204 KB | Output is correct |
31 | Correct | 0 ms | 204 KB | Output is correct |
32 | Correct | 0 ms | 204 KB | Output is correct |
33 | Correct | 1 ms | 204 KB | Output is correct |
34 | Correct | 0 ms | 204 KB | Output is correct |
35 | Correct | 1 ms | 204 KB | Output is correct |
36 | Correct | 7 ms | 1192 KB | Output is correct |
37 | Correct | 168 ms | 24064 KB | Output is correct |
38 | Correct | 1 ms | 296 KB | Output is correct |
39 | Correct | 0 ms | 204 KB | Output is correct |
40 | Correct | 8 ms | 1228 KB | Output is correct |
41 | Correct | 195 ms | 23904 KB | Output is correct |
42 | Correct | 0 ms | 204 KB | Output is correct |
43 | Correct | 1 ms | 296 KB | Output is correct |
44 | Correct | 3 ms | 588 KB | Output is correct |
45 | Correct | 78 ms | 10028 KB | Output is correct |
46 | Correct | 0 ms | 204 KB | Output is correct |
47 | Correct | 0 ms | 296 KB | Output is correct |
48 | Correct | 1 ms | 296 KB | Output is correct |
49 | Correct | 45 ms | 6260 KB | Output is correct |
50 | Correct | 169 ms | 23920 KB | Output is correct |
51 | Correct | 168 ms | 24004 KB | Output is correct |
52 | Correct | 173 ms | 23912 KB | Output is correct |
53 | Correct | 68 ms | 10180 KB | Output is correct |
54 | Correct | 68 ms | 10108 KB | Output is correct |
55 | Correct | 166 ms | 23980 KB | Output is correct |
56 | Correct | 178 ms | 23972 KB | Output is correct |
57 | Correct | 78 ms | 10180 KB | Output is correct |
58 | Correct | 0 ms | 300 KB | Output is correct |
59 | Correct | 0 ms | 204 KB | Output is correct |
60 | Correct | 4 ms | 588 KB | Output is correct |
61 | Correct | 79 ms | 10096 KB | Output is correct |
62 | Correct | 0 ms | 204 KB | Output is correct |
63 | Incorrect | 0 ms | 204 KB | Too many ways to get from 0 to 9, should be 1 found no less than 2 |
64 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 7 ms | 1100 KB | Output is correct |
7 | Correct | 172 ms | 21984 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 8 ms | 1092 KB | Output is correct |
13 | Correct | 167 ms | 22096 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 4 ms | 568 KB | Output is correct |
17 | Correct | 78 ms | 8208 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
20 | Correct | 42 ms | 5764 KB | Output is correct |
21 | Correct | 183 ms | 22288 KB | Output is correct |
22 | Correct | 166 ms | 22156 KB | Output is correct |
23 | Correct | 176 ms | 22024 KB | Output is correct |
24 | Correct | 167 ms | 22184 KB | Output is correct |
25 | Correct | 78 ms | 8228 KB | Output is correct |
26 | Correct | 66 ms | 8268 KB | Output is correct |
27 | Correct | 185 ms | 22040 KB | Output is correct |
28 | Correct | 166 ms | 22084 KB | Output is correct |
29 | Correct | 0 ms | 204 KB | Output is correct |
30 | Correct | 0 ms | 204 KB | Output is correct |
31 | Correct | 0 ms | 204 KB | Output is correct |
32 | Correct | 0 ms | 204 KB | Output is correct |
33 | Correct | 1 ms | 204 KB | Output is correct |
34 | Correct | 0 ms | 204 KB | Output is correct |
35 | Correct | 1 ms | 204 KB | Output is correct |
36 | Correct | 7 ms | 1192 KB | Output is correct |
37 | Correct | 168 ms | 24064 KB | Output is correct |
38 | Correct | 1 ms | 296 KB | Output is correct |
39 | Correct | 0 ms | 204 KB | Output is correct |
40 | Correct | 8 ms | 1228 KB | Output is correct |
41 | Correct | 195 ms | 23904 KB | Output is correct |
42 | Correct | 0 ms | 204 KB | Output is correct |
43 | Correct | 1 ms | 296 KB | Output is correct |
44 | Correct | 3 ms | 588 KB | Output is correct |
45 | Correct | 78 ms | 10028 KB | Output is correct |
46 | Correct | 0 ms | 204 KB | Output is correct |
47 | Correct | 0 ms | 296 KB | Output is correct |
48 | Correct | 1 ms | 296 KB | Output is correct |
49 | Correct | 45 ms | 6260 KB | Output is correct |
50 | Correct | 169 ms | 23920 KB | Output is correct |
51 | Correct | 168 ms | 24004 KB | Output is correct |
52 | Correct | 173 ms | 23912 KB | Output is correct |
53 | Correct | 68 ms | 10180 KB | Output is correct |
54 | Correct | 68 ms | 10108 KB | Output is correct |
55 | Correct | 166 ms | 23980 KB | Output is correct |
56 | Correct | 178 ms | 23972 KB | Output is correct |
57 | Correct | 78 ms | 10180 KB | Output is correct |
58 | Correct | 0 ms | 204 KB | Output is correct |
59 | Correct | 0 ms | 204 KB | Output is correct |
60 | Correct | 0 ms | 296 KB | Output is correct |
61 | Correct | 48 ms | 6196 KB | Output is correct |
62 | Correct | 171 ms | 23920 KB | Output is correct |
63 | Correct | 169 ms | 24008 KB | Output is correct |
64 | Correct | 180 ms | 23956 KB | Output is correct |
65 | Correct | 0 ms | 288 KB | Output is correct |
66 | Correct | 44 ms | 6192 KB | Output is correct |
67 | Correct | 172 ms | 23936 KB | Output is correct |
68 | Correct | 168 ms | 24004 KB | Output is correct |
69 | Correct | 182 ms | 23892 KB | Output is correct |
70 | Correct | 1 ms | 204 KB | Output is correct |
71 | Incorrect | 0 ms | 204 KB | Too many ways to get from 4 to 8, should be 1 found no less than 2 |
72 | Halted | 0 ms | 0 KB | - |