# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
487748 | 2021-11-16T14:19:44 Z | ala2 | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 16 ms | 23784 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[0][v[i][0]]=1; } answer[x][y]=1; answer[y][x]=1; } } if(bb) return 0; build(answer); return 1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 23756 KB | Output is correct |
2 | Incorrect | 11 ms | 23760 KB | Answer gives possible 0 while actual possible 1 |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 23756 KB | Output is correct |
2 | Incorrect | 11 ms | 23760 KB | Answer gives possible 0 while actual possible 1 |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 23784 KB | Output is correct |
2 | Correct | 12 ms | 23776 KB | Output is correct |
3 | Correct | 16 ms | 23756 KB | Output is correct |
4 | Correct | 13 ms | 23756 KB | Output is correct |
5 | Incorrect | 11 ms | 23756 KB | b is not symmetric: b[0][2] (0) != b[2][0] (1) |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23756 KB | Output is correct |
2 | Incorrect | 14 ms | 23760 KB | b is not symmetric: b[0][2] (0) != b[2][0] (1) |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 23756 KB | Output is correct |
2 | Incorrect | 11 ms | 23760 KB | Answer gives possible 0 while actual possible 1 |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 23756 KB | Output is correct |
2 | Incorrect | 11 ms | 23760 KB | Answer gives possible 0 while actual possible 1 |
3 | Halted | 0 ms | 0 KB | - |