제출 #301571

#제출 시각아이디문제언어결과실행 시간메모리
301571jwvg0425슈퍼트리 잇기 (IOI20_supertrees)C++17
96 / 100
264 ms22392 KiB
#include "supertrees.h" #include <vector> #include <set> using namespace std; int cpar[1005]; int tpar[1005]; vector<int> byTree[1005]; int tfind(int x) { if (tpar[x] == x) return x; return tpar[x] = tfind(tpar[x]); } void tmerge(int x, int y) { x = tfind(x); y = tfind(y); tpar[x] = y; } int cfind(int x) { if (cpar[x] == x) return x; return cpar[x] = cfind(cpar[x]); } void cmerge(int x, int y) { x = cfind(x); y = cfind(y); cpar[x] = y; } int construct(vector<vector<int>> p) { int n = p.size(); for (int i = 0; i < n; i++) cpar[i] = tpar[i] = i; vector<vector<int>> answer; for (int i = 0; i < n; i++) { vector<int> row; row.resize(n); answer.push_back(row); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (p[i][j] == 0) continue; if (p[i][j] == 1) { if (tfind(i) == tfind(j)) continue; tmerge(i, j); answer[i][j] = answer[j][i] = 1; continue; } if (p[i][j] == 2) cmerge(i, j); } } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (p[i][j] == 0) { if (cfind(i) == cfind(j) || tfind(i) == tfind(j)) return 0; } if (p[i][j] == 1) { if (tfind(i) != tfind(j)) return 0; } if (p[i][j] == 2) { if (cfind(i) != cfind(j) || tfind(i) == tfind(j)) return 0; } } } for (int i = 0; i < n; i++) { if (cfind(i) != i) continue; vector<int> cs; set<int> ts; for (int j = 0; j < n; j++) { if (cfind(j) != i) continue; cs.push_back(j); ts.insert(tfind(j)); } vector<int> tv; for (auto ti : ts) { tv.push_back(ti); for (auto &x : byTree[ti]) for (auto &y : byTree[ti]) if (p[x][y] != 1) return 0; for (auto &tj : ts) { if (ti == tj) continue; for (auto &x : byTree[ti]) for (auto &y : byTree[tj]) if (p[x][y] != 2) return 0; } } int k = tv.size(); if (k <= 1) continue; if (k == 2) return 0; for (int x = 0; x < k; x++) { int nx = (x + 1) % k; answer[tv[x]][tv[nx]] = answer[tv[nx]][tv[x]] = 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...