Submission #1212728

#TimeUsernameProblemLanguageResultExecution timeMemory
1212728madamadam3Connecting Supertrees (IOI20_supertrees)C++20
11 / 100
110 ms22184 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; #define sz(x) int((x).size()) #define bg(x) (x).begin() #define en(x) (x).end() #define all(x) bg((x)), en((x)) #define FOR(i, a, b) for (int i = a; i < b; i++) #define pb push_back using vi = vector<int>; using vvi = vector<vi>; struct DSU { int n; vector<int> par, siz; DSU(int N) { n = N; par.resize(n); iota(all(par), 0); siz.assign(n, 1); } int find(int v) { if (par[v] == v) return v; return par[v] = find(par[v]); } void unite(int a, int b) { a = find(a); b = find(b); if (a != b) { if (siz[a] < siz[b]) swap(a, b); par[b] = a; siz[a] += siz[b]; } } }; int construct(vvi p) { int n = sz(p); auto dsu = DSU(n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (p[i][j] >= 1) dsu.unite(i, j); } } FOR(i, 0, n) { FOR(j, i+1, n) { if (p[i][j] == 0 && dsu.find(i) == dsu.find(j)) { return -1; } } } vvi cmps(n); FOR(i, 0, n) cmps[dsu.find(i)].pb(i); vvi answer(n, vector<int>(n, 0)); FOR(cmpid, 0, n) { if (sz(cmps[cmpid]) <= 1) continue; int fst = cmps[cmpid][0], prev = cmps[cmpid][0]; FOR(i, 1, sz(cmps[cmpid])) { answer[i][prev] = answer[prev][i] = 1; prev = cmps[cmpid][i]; } if (p[fst][prev] == 2) { answer[fst][prev] = answer[prev][fst] = 1; } } build(answer); 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...