Submission #798160

#TimeUsernameProblemLanguageResultExecution timeMemory
798160nninConnecting Supertrees (IOI20_supertrees)C++14
100 / 100
168 ms22100 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int dsu[1001]; int par(int x) { if(dsu[x]==x) return x; return dsu[x] = par(dsu[x]); } int dsu2[1001]; int par2(int x) { if(dsu2[x]==x) return x; return dsu2[x] = par2(dsu2[x]); } vector<int> cyc[1001]; int construct(std::vector<std::vector<int>> p) { int n = p.size(); vector<vector<int>> answer(n, vector<int>(n, 0)); for(int i=0;i<n;i++) dsu[i] = dsu2[i] = i; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { if(p[i][j]==3) return 0; if(p[i][j]==1) { int pari = par(i); int parj = par(j); if(pari!=parj) { dsu[pari] = parj; answer[pari][parj] = answer[parj][pari] = 1; } } } for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { if(p[i][j]==2) { int pari = par2(par(i)); int parj = par2(par(j)); if(pari!=parj) { dsu2[pari] = parj; } } } for(int i=0;i<n;i++) { if(par(i)==i) cyc[par2(i)].push_back(i); } for(int i=0;i<n;i++) { if(cyc[i].size()<=1) continue; if(cyc[i].size()==2) return 0; int last = cyc[i][cyc[i].size()-1]; for(int cur:cyc[i]) { answer[last][cur] = answer[cur][last] = 1; last = cur; } } for(int i=0;i<n;i++) for(int j=0;j<n;j++) { if(!p[i][j]) { int pari = par(i); int parj = par(j); if(pari==parj || par2(pari)==par2(parj)) { return 0; } } } build(answer); return 1; } /* 4 1 1 2 2 1 1 2 2 2 2 1 2 2 2 2 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...