# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
366617 | 2021-02-14T19:41:09 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; 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])adj[i].pb(j); } } int c[n][n]; int cnt = 0; for(int i = 0;i < n;i++) { for(int j = 0;j<n;j++) { c[i][j] = cnt++; } } for(int i = 0;i < n;i++) { if(!vis[i]){ component.clear(); dfs(i); for(int j = 0;j < sz(component);j++) { for(int k = j + 1;k < sz(component);k++) { c[j][k] = c[k][j] = comp[0]; } } for(int j = 1;j < sz(component);j++) { ans[component[j]][component[j-1]] = ans[component[j-1]][component[j]] = 1; } } } for(int i = 0;i <n;i++) { for(int j = 0;j < n;j++) { if(c[i][j] == c[j][i] !p[i][j])return 0; } } for(int i = 0) build(ans); return 1; }