# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
521242 | 2022-02-01T09:37:46 Z | oneloveforever | Connecting Supertrees (IOI20_supertrees) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long struct DSU { int n; vector<int>trace; DSU(int _n=0) { n=_n; trace.resize(n+7); iota(trace.begin(),trace.end(),0); } int get(int x) { return trace[x]==x?trace[x]:trace[x]=get(trace[x]); } void connect(int x,int y) { int u=get(x); int v=get(y); if(u==v)return ; trace[v]=u; } }; int construct(vector<vector<int> >p) { int n=p.size(); DSU only(n); DSU can(n); for(int i=0;i<=n-1;i++) { for(int j=0;j<=n-1;j++)if(p[i][j]==3)return 0; } vector<vector<int> >b(n,vector<int>(n)); for(int i=0;i<=n-1;i++) { for(int j=i+1;j<=n-1;j++) { if(p[i][j]==1)only.connect(i,j); if(p[i][j])can.connect(i,j); } } for(int i=0;i<=n-1;i++) { if(can.get(i)!=i)continue; vector<int>q; for(int node=0;node<=n-1;node++) { if(can.get(node)==i&&only.get(node)==node)q.push_back(node); } if((int)q.size()==1)continue; if((int)q.size()==2)return 0; for(int node=0;node<=q.size()-2;node++) { int node_x=q[node]; int node_y=q[(node+1)%n]; b[node_x][node_y]=1; b[node_y][node_x]=1; } } for(int i=0;i<=n-1;i++)if(only.get(i)!=i) { int node=only.get(i); b[node][i]=b[i][node]=1; } for(int i=0;i<=n-1;i++) { for(int j=i+1;j<=n-1;j++) { if(only.get(i)==only.get(j)) { if(p[i][j]!=1)return false; } else if(can.get(i)==can.get(j)) { if(p[i][j]!=2)return false; } else { if(p[i][j])return false; } } } build(b); return 1; }