# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
625303 | 2022-08-10T01:06:21 Z | Trunkty | Connecting Supertrees (IOI20_supertrees) | C++14 | 184 ms | 24120 KB |
#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; typedef long long ll; //#define int ll #include "supertrees.h" int root[1005]; vector<int> ans[1005]; int rootp[1005]; vector<int> part[1005]; int findroot(int x){ if(root[x]!=x){ root[x] = findroot(root[x]); } return root[x]; } void domerge(int a, int b){ a = findroot(a); b = findroot(b); root[a] = b; } int findrootp(int x){ if(rootp[x]!=x){ rootp[x] = findrootp(rootp[x]); } return rootp[x]; } void domergep(int a, int b){ a = findrootp(a); b = findrootp(b); rootp[a] = b; } int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> ret; for (int i = 0; i < n; i++) { vector<int> row; row.resize(n); ret.push_back(row); } for(int i=0;i<n;i++){ root[i] = i; rootp[i] = i; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(p[i][j]){ domerge(i,j); } if(p[i][j]==1){ domergep(i,j); } } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(p[i][j]==0 and findroot(i)==findroot(j)){ return 0; } } } for(int i=0;i<n;i++){ ans[findroot(i)].push_back(i); part[findrootp(i)].push_back(i); } for(int i=0;i<n;i++){ for(int j=1;j<part[i].size();j++){ ret[part[i][j-1]][part[i][j]] = 1; ret[part[i][j]][part[i][j-1]] = 1; } } for(int i=0;i<n;i++){ set<int> s; vector<int> v; for(int j=0;j<ans[i].size();j++){ s.insert(findrootp(ans[i][j])); } for(int j:s){ v.push_back(j); } for(int j=1;j<v.size();j++){ ret[v[j]][v[j-1]] = 1; ret[v[j-1]][v[j]] = 1; } if(v.size()<=2){ continue; } ret[v[0]][v.back()] = 1; ret[v.back()][v[0]] = 1; } build(ret); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 7 ms | 1252 KB | Output is correct |
7 | Correct | 184 ms | 22084 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 7 ms | 1252 KB | Output is correct |
7 | Correct | 184 ms | 22084 KB | Output is correct |
8 | Correct | 0 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 0 ms | 340 KB | Output is correct |
11 | Correct | 0 ms | 340 KB | Output is correct |
12 | Correct | 8 ms | 1236 KB | Output is correct |
13 | Correct | 176 ms | 22160 KB | Output is correct |
14 | Correct | 0 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 4 ms | 724 KB | Output is correct |
17 | Correct | 83 ms | 12092 KB | Output is correct |
18 | Correct | 0 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 340 KB | Output is correct |
20 | Correct | 53 ms | 5744 KB | Output is correct |
21 | Correct | 171 ms | 22072 KB | Output is correct |
22 | Correct | 168 ms | 22032 KB | Output is correct |
23 | Correct | 180 ms | 22156 KB | Output is correct |
24 | Correct | 184 ms | 22144 KB | Output is correct |
25 | Correct | 69 ms | 12100 KB | Output is correct |
26 | Correct | 71 ms | 12108 KB | Output is correct |
27 | Correct | 180 ms | 22072 KB | Output is correct |
28 | Correct | 163 ms | 22092 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Incorrect | 0 ms | 340 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 | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 43 ms | 6248 KB | Output is correct |
5 | Correct | 166 ms | 23980 KB | Output is correct |
6 | Correct | 175 ms | 24044 KB | Output is correct |
7 | Correct | 176 ms | 23972 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 50 ms | 6440 KB | Output is correct |
10 | Correct | 167 ms | 24108 KB | Output is correct |
11 | Correct | 162 ms | 23992 KB | Output is correct |
12 | Correct | 179 ms | 24108 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 352 KB | Output is correct |
16 | Correct | 47 ms | 6224 KB | Output is correct |
17 | Correct | 172 ms | 24120 KB | Output is correct |
18 | Correct | 180 ms | 24048 KB | Output is correct |
19 | Correct | 173 ms | 24068 KB | Output is correct |
20 | Correct | 172 ms | 24108 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 7 ms | 1252 KB | Output is correct |
7 | Correct | 184 ms | 22084 KB | Output is correct |
8 | Correct | 0 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 0 ms | 340 KB | Output is correct |
11 | Correct | 0 ms | 340 KB | Output is correct |
12 | Correct | 8 ms | 1236 KB | Output is correct |
13 | Correct | 176 ms | 22160 KB | Output is correct |
14 | Correct | 0 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 4 ms | 724 KB | Output is correct |
17 | Correct | 83 ms | 12092 KB | Output is correct |
18 | Correct | 0 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 340 KB | Output is correct |
20 | Correct | 53 ms | 5744 KB | Output is correct |
21 | Correct | 171 ms | 22072 KB | Output is correct |
22 | Correct | 168 ms | 22032 KB | Output is correct |
23 | Correct | 180 ms | 22156 KB | Output is correct |
24 | Correct | 184 ms | 22144 KB | Output is correct |
25 | Correct | 69 ms | 12100 KB | Output is correct |
26 | Correct | 71 ms | 12108 KB | Output is correct |
27 | Correct | 180 ms | 22072 KB | Output is correct |
28 | Correct | 163 ms | 22092 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Incorrect | 0 ms | 340 KB | Answer gives possible 1 while actual possible 0 |
33 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 7 ms | 1252 KB | Output is correct |
7 | Correct | 184 ms | 22084 KB | Output is correct |
8 | Correct | 0 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 0 ms | 340 KB | Output is correct |
11 | Correct | 0 ms | 340 KB | Output is correct |
12 | Correct | 8 ms | 1236 KB | Output is correct |
13 | Correct | 176 ms | 22160 KB | Output is correct |
14 | Correct | 0 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 4 ms | 724 KB | Output is correct |
17 | Correct | 83 ms | 12092 KB | Output is correct |
18 | Correct | 0 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 340 KB | Output is correct |
20 | Correct | 53 ms | 5744 KB | Output is correct |
21 | Correct | 171 ms | 22072 KB | Output is correct |
22 | Correct | 168 ms | 22032 KB | Output is correct |
23 | Correct | 180 ms | 22156 KB | Output is correct |
24 | Correct | 184 ms | 22144 KB | Output is correct |
25 | Correct | 69 ms | 12100 KB | Output is correct |
26 | Correct | 71 ms | 12108 KB | Output is correct |
27 | Correct | 180 ms | 22072 KB | Output is correct |
28 | Correct | 163 ms | 22092 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Incorrect | 0 ms | 340 KB | Answer gives possible 1 while actual possible 0 |
33 | Halted | 0 ms | 0 KB | - |