# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
487749 | 2021-11-16T14:20:29 Z | ala2 | Connecting Supertrees (IOI20_supertrees) | C++14 | 194 ms | 45524 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]) { //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]&&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++) { answer[i][i]=0; if(i!=root(i)) continue; // cout<<v[i].size()<<endl; if(v[i].size()==2) bb=1; 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<<" "; if(i==v[i].size()-2) { answer[y][v[i][0]]=1; answer[v[i][0]][y]=1; } answer[x][y]=1; answer[y][x]=1; } } if(bb) return 0; build(answer); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 23812 KB | Output is correct |
2 | Incorrect | 11 ms | 23756 KB | Answer gives possible 0 while actual possible 1 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 23812 KB | Output is correct |
2 | Incorrect | 11 ms | 23756 KB | Answer gives possible 0 while actual possible 1 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 23756 KB | Output is correct |
2 | Correct | 15 ms | 23756 KB | Output is correct |
3 | Correct | 14 ms | 23728 KB | Output is correct |
4 | Correct | 14 ms | 23756 KB | Output is correct |
5 | Correct | 14 ms | 23808 KB | Output is correct |
6 | Correct | 12 ms | 23716 KB | Output is correct |
7 | Correct | 14 ms | 23704 KB | Output is correct |
8 | Correct | 22 ms | 24676 KB | Output is correct |
9 | Correct | 194 ms | 45524 KB | Output is correct |
10 | Incorrect | 12 ms | 23756 KB | Too few ways to get from 0 to 1, should be 2 found 1 |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 23724 KB | Output is correct |
2 | Correct | 14 ms | 23756 KB | Output is correct |
3 | Incorrect | 14 ms | 23708 KB | Too many ways to get from 1 to 3, should be 1 found no less than 2 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 23812 KB | Output is correct |
2 | Incorrect | 11 ms | 23756 KB | Answer gives possible 0 while actual possible 1 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 23812 KB | Output is correct |
2 | Incorrect | 11 ms | 23756 KB | Answer gives possible 0 while actual possible 1 |
3 | Halted | 0 ms | 0 KB | - |