Submission #981495

#TimeUsernameProblemLanguageResultExecution timeMemory
981495tamir1Connecting Supertrees (IOI20_supertrees)C++17
0 / 100
1 ms348 KiB
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; int sz[1001],par[1001]; int find(int a){ if(a==par[a]) return a; int x=find(par[a]); par[a]=x; return x; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); for(int i=0;i<n;i++){ sz[i]=1; par[i]=i; for(int j=0;j<n;j++){ if(p[i][j]==3) return 0; } } if(n==1){ build({{0}}); return 1; } std::vector<std::vector<int>> answer(n,vector<int> (n,0)); for (int i = 0; i < n; i++) { for(int j=0;j<n;j++){ int x=find(i); int y=find(j); if(p[i][j]==0 && x==y) return 0; if(p[i][j]==1){ if(x==y) continue; if(sz[x]<sz[y]) swap(x,y); else if(sz[x]==sz[y] && x>y) swap(x,y); sz[x]+=sz[y]; par[y]=x; } } } 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...