# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
366620 | 2021-02-14T19:47:32 Z | SlavicG | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KB |
#include "supertrees.h" #include "bits/stdc++.h" using namespace std; #define ll long long #define forn(i,n) for(int i=0;i<n;i++) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(),v.rend() #define pb push_back #define sz(a) (int)a.size() #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 1001; vector<int> adj[N]; bool vis[N]; vector<int> component; int par[N]; int get(int a){ while(par[a]!=a)a=par[a]; return a; } void uni(int a,int b){ if(a==b)return; par[b] = a; } void dfs(int u) { vis[u] = true; component.pb(u); for(auto x : adj[u]){ if(!vis[x])dfs(x); } } int construct(vector<vector<int>> p) { int n = sz(p); vector<vector<int>> ans; ans.resize(n); for(int i =0;i < n;i++)ans[i].resize(n); forn(i,n)forn(j,n)ans[i][j]=0; for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { if(p[i][j]){ uni(a,b); adj[i].pb(j); } } } for(int i = 0;i < n;i++) { for(int j =0;j < n;j++) { if(get(a)==get(b) && !p[i][j])return 0; } } for(int i = 0;i < n;i++) { if(!vis[i]){ component.clear(); dfs(i); for(int j = 1;j < sz(component);j++) { ans[component[j]][component[j-1]] = ans[component[j-1]][component[j]] = 1; } } } build(ans); return 1; }