제출 #1149052

#제출 시각아이디문제언어결과실행 시간메모리
1149052blackslexConnecting Supertrees (IOI20_supertrees)C++20
46 / 100
131 ms22188 KiB
#include "supertrees.h" #include <vector> #include<bits/stdc++.h> using namespace std; int construct(std::vector<std::vector<int>> p) { int n = p.size(); std::vector<std::vector<int>> answer(n, vector<int>(n)); auto add = [&] (int x, int y) { answer[x][y] = answer[y][x] = 1; }; vector<int> par(n), par2(n); iota(par.begin(), par.end(), 0); iota(par2.begin(), par2.end(), 0); function<int(int)> fset = [&] (int x) {return (par[x] == x ? x : par[x] = fset(par[x]));}; function<int(int)> fset2 = [&] (int x) {return (par2[x] == x ? x : par2[x] = fset2(par2[x]));}; auto mg = [&] (int x, int y) { if ((x = fset(x)) == (y = fset(y))) return; par[y] = x; }; auto mg2 = [&] (int x, int y) { if ((x = fset2(x)) == (y = fset2(y))) return; par2[y] = x; }; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (p[i][j]) mg(i, j); } } for (int i = 0; i < n; i++) { if (fset(i) != i) continue; vector<int> c, cc; for (int j = 0; j < n; j++) { if (fset(j) == i) c.emplace_back(j); } int csz = c.size(); for (int j = 0; j < csz; j++) { for (int k = 0; k < csz; k++) { if (c[j] != c[k] && p[c[j]][c[k]] == 1) mg2(c[j], c[k]); } } for (int j = 0; j < csz; j++) { if (fset2(c[j]) != c[j]) continue; cc.emplace_back(c[j]); vector<int> c2; for (int k = 0; k < csz; k++) { if (fset2(c[k]) == c[j]) c2.emplace_back(c[k]); } int csz2 = c2.size(); for (int k = 0; k < csz2 - 1; k++) { add(c2[k], c2[k + 1]); } } sort(cc.begin(), cc.end()); cc.resize(unique(cc.begin(), cc.end()) - cc.begin()); int ccsz = cc.size(); for (int j = 0; j < ccsz; j++) { add(cc[j], cc[(j + 1) % ccsz]); } } for (int i = 0; i < n; i++) { answer[i][i] = 0; } 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...