# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
487739 | 2021-11-16T14:05:08 Z | ala2 | Connecting Supertrees (IOI20_supertrees) | C++14 | 199 ms | 47628 KB |
#include "supertrees.h" #include <vector> #include<iostream> using namespace std; int pa[1001000]; int sz[1001000]; int root(int x) { while(x!=pa[x]) { pa[x]=pa[pa[x]]; x=pa[x]; } return x; } void unit(int x,int y) { x=root(x); y=root(y); if(x==y) return ; if(sz[x]>sz[y]) { sz[x]+=sz[y]; pa[y]=x; } else { sz[y]+=sz[x]; pa[x]=y; } } vector<int>v[1001000]; int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> answer; for (int i = 0; i < n; i++) { vector<int> row; row.resize(n); answer.push_back(row); } for(int i=0;i<n;i++) { pa[i]=i; sz[i]=1; } int bb=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(p[i][j]==1) { //cout<<" "<<i<<" " <<j<<" "<<root(i)<<" "<<root(j)<<" "; unit(i,j); // cout<<root(i)<<endl; } } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(p[i][j]==1&&root(i)!=root(j)) bb=1; if(p[i][j]==0&&root(i)==root(j)) bb=1; } } for(int i=0;i<n;i++) { // cout<<" "<<i<<" "<<root(i)<<endl; v[root(i)].push_back(i); } for(int i=0;i<n;i++) { if(i!=root(i)) continue; // cout<<v[i].size()<<endl; for(int j=0;j<v[i].size()-1;j++) { int x=v[i][j]; int y=v[i][j+1]; // cout<<x<<" "; // if(j==v[i].size()-1) // cout<<y<<" "; answer[x][y]=1; answer[y][x]=1; } cout<<endl; } if(bb) return 0; build(answer); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23756 KB | Output is correct |
2 | Correct | 15 ms | 23820 KB | Output is correct |
3 | Correct | 12 ms | 23736 KB | Output is correct |
4 | Correct | 12 ms | 23756 KB | Output is correct |
5 | Correct | 13 ms | 23792 KB | Output is correct |
6 | Correct | 20 ms | 24704 KB | Output is correct |
7 | Correct | 191 ms | 45568 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23756 KB | Output is correct |
2 | Correct | 15 ms | 23820 KB | Output is correct |
3 | Correct | 12 ms | 23736 KB | Output is correct |
4 | Correct | 12 ms | 23756 KB | Output is correct |
5 | Correct | 13 ms | 23792 KB | Output is correct |
6 | Correct | 20 ms | 24704 KB | Output is correct |
7 | Correct | 191 ms | 45568 KB | Output is correct |
8 | Correct | 12 ms | 23756 KB | Output is correct |
9 | Correct | 14 ms | 23736 KB | Output is correct |
10 | Correct | 15 ms | 23760 KB | Output is correct |
11 | Correct | 14 ms | 23800 KB | Output is correct |
12 | Correct | 21 ms | 24692 KB | Output is correct |
13 | Correct | 183 ms | 47628 KB | Output is correct |
14 | Correct | 14 ms | 23760 KB | Output is correct |
15 | Correct | 12 ms | 23816 KB | Output is correct |
16 | Correct | 15 ms | 24344 KB | Output is correct |
17 | Correct | 111 ms | 37584 KB | Output is correct |
18 | Correct | 15 ms | 23760 KB | Output is correct |
19 | Correct | 12 ms | 23760 KB | Output is correct |
20 | Correct | 56 ms | 29780 KB | Output is correct |
21 | Correct | 188 ms | 47452 KB | Output is correct |
22 | Correct | 180 ms | 47452 KB | Output is correct |
23 | Correct | 196 ms | 47452 KB | Output is correct |
24 | Correct | 179 ms | 47452 KB | Output is correct |
25 | Correct | 93 ms | 37588 KB | Output is correct |
26 | Correct | 86 ms | 37576 KB | Output is correct |
27 | Correct | 199 ms | 47440 KB | Output is correct |
28 | Correct | 178 ms | 47560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 23756 KB | Output is correct |
2 | Correct | 11 ms | 23760 KB | Output is correct |
3 | Correct | 12 ms | 23760 KB | Output is correct |
4 | Incorrect | 12 ms | 23768 KB | Answer gives possible 1 while actual possible 0 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 23756 KB | Output is correct |
2 | Incorrect | 14 ms | 23760 KB | Too few ways to get from 0 to 1, should be 2 found 0 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23756 KB | Output is correct |
2 | Correct | 15 ms | 23820 KB | Output is correct |
3 | Correct | 12 ms | 23736 KB | Output is correct |
4 | Correct | 12 ms | 23756 KB | Output is correct |
5 | Correct | 13 ms | 23792 KB | Output is correct |
6 | Correct | 20 ms | 24704 KB | Output is correct |
7 | Correct | 191 ms | 45568 KB | Output is correct |
8 | Correct | 12 ms | 23756 KB | Output is correct |
9 | Correct | 14 ms | 23736 KB | Output is correct |
10 | Correct | 15 ms | 23760 KB | Output is correct |
11 | Correct | 14 ms | 23800 KB | Output is correct |
12 | Correct | 21 ms | 24692 KB | Output is correct |
13 | Correct | 183 ms | 47628 KB | Output is correct |
14 | Correct | 14 ms | 23760 KB | Output is correct |
15 | Correct | 12 ms | 23816 KB | Output is correct |
16 | Correct | 15 ms | 24344 KB | Output is correct |
17 | Correct | 111 ms | 37584 KB | Output is correct |
18 | Correct | 15 ms | 23760 KB | Output is correct |
19 | Correct | 12 ms | 23760 KB | Output is correct |
20 | Correct | 56 ms | 29780 KB | Output is correct |
21 | Correct | 188 ms | 47452 KB | Output is correct |
22 | Correct | 180 ms | 47452 KB | Output is correct |
23 | Correct | 196 ms | 47452 KB | Output is correct |
24 | Correct | 179 ms | 47452 KB | Output is correct |
25 | Correct | 93 ms | 37588 KB | Output is correct |
26 | Correct | 86 ms | 37576 KB | Output is correct |
27 | Correct | 199 ms | 47440 KB | Output is correct |
28 | Correct | 178 ms | 47560 KB | Output is correct |
29 | Correct | 12 ms | 23756 KB | Output is correct |
30 | Correct | 11 ms | 23760 KB | Output is correct |
31 | Correct | 12 ms | 23760 KB | Output is correct |
32 | Incorrect | 12 ms | 23768 KB | Answer gives possible 1 while actual possible 0 |
33 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23756 KB | Output is correct |
2 | Correct | 15 ms | 23820 KB | Output is correct |
3 | Correct | 12 ms | 23736 KB | Output is correct |
4 | Correct | 12 ms | 23756 KB | Output is correct |
5 | Correct | 13 ms | 23792 KB | Output is correct |
6 | Correct | 20 ms | 24704 KB | Output is correct |
7 | Correct | 191 ms | 45568 KB | Output is correct |
8 | Correct | 12 ms | 23756 KB | Output is correct |
9 | Correct | 14 ms | 23736 KB | Output is correct |
10 | Correct | 15 ms | 23760 KB | Output is correct |
11 | Correct | 14 ms | 23800 KB | Output is correct |
12 | Correct | 21 ms | 24692 KB | Output is correct |
13 | Correct | 183 ms | 47628 KB | Output is correct |
14 | Correct | 14 ms | 23760 KB | Output is correct |
15 | Correct | 12 ms | 23816 KB | Output is correct |
16 | Correct | 15 ms | 24344 KB | Output is correct |
17 | Correct | 111 ms | 37584 KB | Output is correct |
18 | Correct | 15 ms | 23760 KB | Output is correct |
19 | Correct | 12 ms | 23760 KB | Output is correct |
20 | Correct | 56 ms | 29780 KB | Output is correct |
21 | Correct | 188 ms | 47452 KB | Output is correct |
22 | Correct | 180 ms | 47452 KB | Output is correct |
23 | Correct | 196 ms | 47452 KB | Output is correct |
24 | Correct | 179 ms | 47452 KB | Output is correct |
25 | Correct | 93 ms | 37588 KB | Output is correct |
26 | Correct | 86 ms | 37576 KB | Output is correct |
27 | Correct | 199 ms | 47440 KB | Output is correct |
28 | Correct | 178 ms | 47560 KB | Output is correct |
29 | Correct | 12 ms | 23756 KB | Output is correct |
30 | Correct | 11 ms | 23760 KB | Output is correct |
31 | Correct | 12 ms | 23760 KB | Output is correct |
32 | Incorrect | 12 ms | 23768 KB | Answer gives possible 1 while actual possible 0 |
33 | Halted | 0 ms | 0 KB | - |