Submission #1212163

#TimeUsernameProblemLanguageResultExecution timeMemory
1212163jumpConnecting Supertrees (IOI20_supertrees)C++20
21 / 100
131 ms22272 KiB
#include "supertrees.h" #include <vector> #include <map> int dsu0[1010]; int dsu1[1010]; int findSet0(int a){ if(dsu0[a]==a)return a; else return dsu0[a]=findSet0(dsu0[a]); } void unionSet0(int a,int b){ int A = findSet0(a); int B = findSet0(b); if(A==B)return; dsu0[A]=B; } int findSet1(int a){ if(dsu0[a]==a)return a; else return dsu0[a]=findSet0(dsu0[a]); } void unionSet1(int a,int b){ int A = findSet0(a); int B = findSet0(b); if(A==B)return; dsu0[A]=B; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); std::vector<std::vector<int>> answer; for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); answer.push_back(row); } for(int i=0;i<=1000;i++){ dsu0[i]=i; dsu1[i]=i; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==j){ if(p[i][j]==1)continue; else return 0; } if(p[i][j]>0)unionSet0(i,j); if(p[i][j]==3)return 0; if(p[i][j]==0&&findSet0(i)==findSet0(j))return 0; } } std::map<int,std::vector<int>> m; for(int i=0;i<n;i++){ m[findSet0(i)].push_back(i); } for(auto& [id,com]:m){ for(int ci=0;ci<com.size();ci++){ for(int cj=0;cj<com.size();cj++){ if(ci==cj)continue; int i = com[ci]; int j = com[cj]; if(p[i][j]==1)unionSet1(i,j); if(p[i][j]==2&&findSet1(i)==findSet1(j))return 0; } } for(int ci=0;ci<com.size();ci++){ for(int cj=0;cj<com.size();cj++){ int i = com[ci]; int j = com[cj]; if(p[i][j]==2){ answer[i][j]=answer[j][i]=1; } if(p[i][j]==1){ answer[i][findSet1(j)]=1; answer[j][findSet1(i)]=1; answer[findSet1(j)][i]=1; answer[findSet1(i)][j]=1; } } } } for(int i=0;i<n;i++)answer[i][i]=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...