Submission #1255033

#TimeUsernameProblemLanguageResultExecution timeMemory
1255033minggaConnecting Supertrees (IOI20_supertrees)C++20
40 / 100
238 ms22228 KiB
// Author: caption_mingle #include "bits/stdc++.h" #include "supertrees.h" using namespace std; #define ln "\n" #define pb push_back #define fi first #define se second #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define ll long long const int mod = 1e9 + 7; const int inf = 2e9; struct DSU { int n; vector<int> par,sz; DSU() {} DSU(int n) : n(n) { par.resize(n, 0); sz.resize(n, 1); for(int i = 1; i < n; i++) par[i] = i; } int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); } void join(int u, int v) { u = find(u), v = find(v); if(u == v) return; if(sz[u] < sz[v]) swap(u, v); sz[u] += sz[v]; par[v] = u; } }; int construct(vector<vector<int>> p) { int n = sz(p); vector<vector<int>> ans(n, vector<int>(n, 0)); DSU d(n); for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(p[i][j] == 3) return 0; if(p[i][j]) d.join(i, j); } } vector<vector<int>> gp(n); for(int i = 0; i < n; i++) { gp[d.find(i)].pb(i); for(int j = 1; j < n; j++) { if(d.find(i) == d.find(j) and p[i][j] == 0) return 0; } } for(int i = 0; i < n; i++) { if(sz(gp[i]) <= 1) continue; bool check1 = 1; if(sz(gp[i]) >= 3) { for(int j = 0; j < sz(gp[i]); j++) { int u = gp[i][j]; for(int k = j + 1; k < sz(gp[i]); k++) { int v = gp[i][k]; for(int t = k + 1; t < sz(gp[i]); t++) { int w = gp[i][t]; if(p[u][v] * p[v][w] * p[u][w] == 2) return 0; if(p[u][v] * p[v][w] * p[u][w] != 1) check1 = 0; } } } } else if(p[gp[i][0]][gp[i][1]] == 2) return 0; if(check1) { for(int j = 1; j < sz(gp[i]); j++) { ans[gp[i][j]][gp[i][j - 1]] = 1; ans[gp[i][j - 1]][gp[i][j]] = 1; } continue; } int st = -1; vector<bool> mark(n, 0); for(int j = 0; j < sz(gp[i]); j++) { int u = gp[i][j]; for(int k = j + 1; k < sz(gp[i]); k++) { int v = gp[i][k]; if(p[u][v] == 2) { st = u; break; } } if(st != -1) break; } vector<int> circle; circle.pb(st); while(1) { bool ok = 0; int cur = circle.back(); for(int j = 0; j < sz(gp[i]); j++) { int u = gp[i][j]; if(mark[u]) continue; ok = 1; for(int v : circle) { if(p[u][v] == 1) { ok = 0; break; } } if(ok) { circle.pb(u), mark[u] = 1; break; } } if(!ok) break; } if(sz(circle) < 3) return 0; ans[circle[0]][circle.back()] = 1; ans[circle.back()][circle[0]] = 1; for(int j = 1; j < sz(circle); j++) { int u = circle[j]; ans[u][circle[j - 1]] = 1; ans[circle[j - 1]][u] = 1; for(int k = 0; k < sz(gp[i]); k++) { int v = gp[i][k]; if(mark[v]) continue; if(p[u][v] == 1) { ans[u][v] = 1; ans[v][u] = 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...