# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
486525 | 2021-11-11T21:57:25 Z | A_D | Connecting Supertrees (IOI20_supertrees) | C++14 | 0 ms | 0 KB |
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int N=1e3+100; vector<int> g[N]; vector<int> g2[N]; bool vis[N]; bool ccc[N]; vector<vector<int>> answer; int pp[N]; int c[N]; vector<int> vec; vector<int> vec2; int ret=1; int find(int u) { if(u==pp[u])return u; return pp[u]=find(pp[u]); } bool ok() { for(int i=1;i<vec2.size();i++){ for(int j=0;j<n;j++){ if(vec2[i]==j||vec2[i-1]==j)continue; if(p[vec2[i]][j]!=p[vec2[i-1]][j])return 1; } } return 0; } void dfs(int u) { vec2.push_back(u); if(vis[u])return; vis[u]=1; for(auto x:g[u]){ if(vis[x])continue; answer[u][x]=1; answer[x][u]=1; pp[find(u)]=pp[find(x)]; dfs(x); } } int construct(vector<vector<int>> p) { int n = p.size(); for (int i = 0; i < n; i++) { pp[i]=i; vector<int> row(n); answer.push_back(row); } for(int i=0;i<n;i++){ if(p[i][i]!=1)return 0; for(int j=0;j<n;j++){ if(p[i][j]==1){ g[i].push_back(j); g[j].push_back(i); } } } for(int i=0;i<n;i++){ dfs(i); if(ok())return 0; vec2.clear(); } for(int i=0;i<n;i++){ if(pp[i]==i)vec.push_back(i); } int sz=vec.size(); for(int i1=0;i1<sz;i1++){ for(int j1=i1+1;j1<sz;j1++){ int i=vec[i1]; int j=vec[j1]; ccc[i]=1; if(p[i][j]==3)return -1; if(p[i][j]==2){ answer[i][j]=1; answer[j][i]=1; break; } } } for(int i1=0;i1<sz;i1++){ for(int j1=sz-1;j1>i1;j1--){ int i=vec[i1]; int j=vec[j1]; if(p[i][j]==2&&ccc[j]==0){ ccc[j]=1; answer[i][j]++; answer[j][i]++; if(answer[i][j]==2){ // cout<<i<<" "<<j<<endl; return 0; } break; } } } build(answer); return 1; }