# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
487756 | 2021-11-16T14:25:35 Z | ala2 | Connecting Supertrees (IOI20_supertrees) | C++14 | 11 ms | 23756 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; answer[i][i]=0; // 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; } } for(int i=0;i<n;i++) { answer[i][i]=1; } if(bb) return 0; build(answer); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 23756 KB | b[0][0] is not 0 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 23756 KB | b[0][0] is not 0 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 23756 KB | b[0][0] is not 0 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 23756 KB | b[0][0] is not 0 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 23756 KB | b[0][0] is not 0 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 23756 KB | b[0][0] is not 0 |
2 | Halted | 0 ms | 0 KB | - |