제출 #351906

#제출 시각아이디문제언어결과실행 시간메모리
351906BlancaHM슈퍼트리 잇기 (IOI20_supertrees)C++14
11 / 100
298 ms24300 KiB
#include <iostream> #include <vector> #include <unordered_map> #include "supertrees.h" using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; int root(int a, vector<int> & parent) { if (a == parent[a]) return a; return parent[a] = root(parent[a], parent); } void merge(int i, int j, vector<int> & parent, vector<int> & rnk, int & numCCs) { int root_i = root(i, parent), root_j = root(j, parent); if (root_i == root_j) return; numCCs--; if (rnk[i] != rnk[j]) { if (rnk[i] > rnk[j]) parent[root_j] = parent[root_i]; else parent[root_i] = parent[root_j]; } else { parent[root_i] = parent[root_j]; rnk[j]++; } } int construct(vvi p) { int N = (int) p.size(), numCCs = N; vector<int> parent(N), rnk(N, 0); for (int i = 0; i < N; i++) parent[i] = i; for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { if (p[i][j]) { if (p[i][j] == 3) { return 0; } merge(i, j, parent, rnk, numCCs); } else if (root(i, parent) == root(j, parent)) return 0; } } unordered_map<int, int> roots; int c = 0; for (int i = 0; i < N; i++) { if (parent[i] == i) roots[i] = c++; } vvi CCs(numCCs, vi()); for (int i = 0; i < N; i++) CCs[roots[root(i, parent)]].push_back(i); int CCsize, u, v, n, root_u, root_v; vi parentCC; vvi result(N, vi(N, 0)), oneTails; for (int i = 0; i < numCCs; i++) { CCsize = (int) CCs[i].size(); n = CCsize; if (CCsize == 1) continue; parentCC = vi(CCsize); rnk.assign(CCsize, 0); for (int j = 0; j < CCsize; j++) parentCC[j] = j; for (int j = 0; j < CCsize; j++) { for (int k = j+1; k < CCsize; k++) { u = CCs[i][j]; v = CCs[i][k]; if (p[u][v] == 1) merge(u, v, parentCC, rnk, n); else if (root(u, parentCC) == root(v, parentCC)) return 0; } } roots.clear(); c = 0; for (int j = 0; j < CCsize; j++) { u = CCs[i][j]; root_u = root(u, parentCC); if (root_u == j) roots[j] = c++; for (int k = j+1; k < CCsize; k++) { v = CCs[i][k]; root_v = root(v, parentCC); if (root_u != root_v) { if (p[u][v] != 2) return 0; } else if (p[u][v] != 1) return 0; } } if (n == 2) return 0; oneTails = vvi(n, vi()); for (int j = 0; j < CCsize; j++) oneTails[roots[root(CCs[i][j], parentCC)]].push_back(CCs[i][j]); for (int j = 0; j < n; j++) { for (int k = 0; k < (int) oneTails[j].size() - 1; k++) result[oneTails[j][k]][oneTails[j][k+1]] = result[oneTails[j][k+1]][oneTails[j][k]] = 1; } // oneTails formed and tails connected inside the tail as a snake for (int j = 0; j < n-1; j++) result[oneTails[j][0]][oneTails[j+1][0]] = result[oneTails[j+1][0]][oneTails[j][0]] = 1; if (n > 1) result[oneTails[0][0]][oneTails[n-1][0]] = result[oneTails[n-1][0]][oneTails[0][0]] = 1; } build(result); 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...