Submission #301003

#TimeUsernameProblemLanguageResultExecution timeMemory
301003ElyesChaabouniConnecting Supertrees (IOI20_supertrees)C++14
0 / 100
1 ms384 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int anc[200000], anc1[200000]; void get_anc(int x) { int cu=anc[x]; while(cu!=anc[cu]) cu=anc[cu]; anc[x]=cu; } void unite(int x, int y) { get_anc(x); get_anc(y); anc[anc[y]]=anc[x]; anc[y]=anc[x]; } void get_anc1(int x) { int cu=anc1[x]; while(cu!=anc1[cu]) cu=anc1[cu]; anc1[x]=cu; } void unite1(int x, int y) { get_anc1(x); get_anc1(y); anc1[anc1[y]]=anc1[x]; anc1[y]=anc1[x]; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); std::vector<std::vector<int>> ans; for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); ans.push_back(row); } for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) ans[i][j]=0; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(p[i][j]==1) unite(i, j); } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { get_anc(i); get_anc(j); if((anc[i]==anc[j] && p[i][j]!=1 )||(anc[i]!=anc[j] && p[i][j]==1 )) return 0; if(p[i][j]==3) return 0; } } for(int i = 0; i < n; i++) { vector<int>v; for(int j = 0; j < n; j++) { if(anc[j]==i) v.push_back(j); } for(int j = 0; j < (int)(v.size())-1; j++) { ans[v[j]][v[j+1]]=1; ans[v[j+1]][v[j]]=1; } } for(int i = 0; i < n; i++) anc1[i]=-1; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(p[i][j]==2) { get_anc(i); get_anc(j); unite1(anc[i], anc[j]); } } } for(int i = 0; i < n; i++) { vector<int>v; for(int j = 0; j < n; j++) { if(anc1[j]==i) v.push_back(j); } for(int j = 0; j < (int)(v.size())-1; j++) { ans[v[j]][v[j+1]]=1; ans[v[j+1]][v[j]]=1; } if(v.size() == 2) return 0; ans[v[0]][v[n-1]]=1; ans[v[n-1]][v[0]]=1; } build(ans); 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...