제출 #579704

#제출 시각아이디문제언어결과실행 시간메모리
579704Clan328슈퍼트리 잇기 (IOI20_supertrees)C++17
56 / 100
336 ms24108 KiB
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; vector<int> link, sz; int find(int x) { if (link[x] != x) link[x] = find(link[x]); return link[x]; } bool same(int a, int b) { return find(a) == find(b); } void unite(int a, int b) { if (a > b) swap(a, b); int x = find(b), y = find(a); if (same(x, y)) return; sz[y] += sz[x]; link[x] = y; } int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> answer(n, vector<int>(n)); link = vector<int>(n); sz = vector<int>(n, 1); iota(link.begin(), link.end(), 0); bool res = true; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) res &= p[i][j] == 1; else if (p[i][j] == 1) unite(i, j); else if (p[i][j] == 3) res = false; } } for (int i = 0; i < n; i++) { int par = find(i); if (par != i) { answer[par][i] = 1; answer[i][par] = 1; for (int j = 0; j < n; j++) { res &= p[i][j] == p[par][j]; } } } vector<set<int>> newNodes(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; if (p[i][j] == 2) { int p1 = find(i), p2 = find(j); unite(p1, p2); newNodes[find(p1)].insert(p1); newNodes[find(p2)].insert(p2); } } } for (int i = 0; i < n; i++) { if (newNodes[i].size() == 0) continue; res &= newNodes[i].size() > 2; for (auto it = newNodes[i].begin(); it != newNodes[i].end(); it++) { auto nxt = it; nxt++; if (nxt == newNodes[i].end()) { nxt = newNodes[i].begin(); } answer[*it][*nxt] = 1; answer[*nxt][*it] = 1; } } if (res) { build(answer); return 1; } else return 0; }
#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...