Submission #300294

#TimeUsernameProblemLanguageResultExecution timeMemory
300294jtnydv25Connecting Supertrees (IOI20_supertrees)C++17
56 / 100
338 ms24868 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; #define all(c) ((c).begin()), ((c).end()) struct dsu{ vector<vector<int>> components; int n; vector<int> par; dsu(int n) : n(n), par(n){ iota(all(par), 0); components.resize(n); for(int i = 0; i < n; i++) components[i] = {i}; } int root(int x){ return x == par[x] ? x : (par[x] = root(par[x])); } void merge(int x, int y){ x = root(x); y = root(y); if(x == y) return; copy(all(components[x]), back_inserter(components[y])); components[x].clear(); par[x] = y; } }; int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> adj(n, vector<int>(n, 0)); function<void(int, int)> add_edge = [&](int x, int y){ adj[x][y] = adj[y][x] = 1; }; dsu D(n); for(int i = 0; i < n; i++){ if(p[i][i] != 1) return 0; for(int j = i + 1; j < n; j++){ if(p[i][j] != p[j][i]) return 0; if(p[i][j] > 0) D.merge(i, j); } } for(int i = 0; i < n; i++) if(D.par[i] == i){ vector<int> v = D.components[i]; for(int x : v) for(int y : v) if(p[x][y] == 0 || p[x][y] == 3) return 0; dsu D2(n); for(int x : v) for(int y : v) if(x != y && p[x][y] == 1) D2.merge(x, y); vector<int> cycle; for(int x : v) if(D2.par[x] == x){ cycle.push_back(x); vector<int> U = D2.components[x]; int lst = -1; for(int a : U){ for(int b : U) if(p[a][b] != 1) return 0; if(lst != -1) add_edge(a, lst); lst = a; } } int m = cycle.size(); if(m > 1) for(int k = 0; k < m; k++) add_edge(cycle[k], cycle[(k + 1) % m]); } build(adj); 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...