Submission #1078715

#TimeUsernameProblemLanguageResultExecution timeMemory
1078715Faisal_SaqibConnecting Supertrees (IOI20_supertrees)C++17
21 / 100
942 ms35904 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int N=1e3; int reach[N][N],tree_case[N][N]; int par[N]; void init(int n) { for(int i=0;i<n;i++) par[i]=i; } int get(int x) { if(par[x]==x)return x; return par[x]=get(par[x]); } bool merge(int x,int y) { x=get(x); y=get(y); if(x==y)return 0; par[y]=x; return 1; } vector<int> ma[N]; int head; void dfs(int x) { reach[head][x]=1; for(auto y:ma[x]) if(!reach[head][y]) dfs(y); } int construct(std::vector<std::vector<int>> p) { int n = p.size(); init(n); for(int i=0;i<n;i++) for(int j=0;j<n;j++) tree_case[i][j]=reach[i][j]=0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(p[i][j]==1) { tree_case[i][j]=tree_case[j][i]=merge(i,j); ma[i].push_back(j); ma[j].push_back(i); } } } vector<vector<int>> answer(n,vector<int>(n,0)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { answer[i][j]=tree_case[i][j]; reach[i][j]=0; } head=i; dfs(i); for(int j=0;j<n;j++) { if(reach[i][j]!=p[i][j]) { return 0; } } } build(answer); return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...