제출 #417496

#제출 시각아이디문제언어결과실행 시간메모리
417496Chaska슈퍼트리 잇기 (IOI20_supertrees)C++17
21 / 100
257 ms27972 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int N = 1e3+5; int n ; int a[N][N]; int dad[N]; bool vs[N]; bool act[N]; struct UnionFind { int ran; int da; }; UnionFind uf[N]; vector<std::vector<int>> answer; vector<int> g[N]; int bus(int u) { if (uf[u].da != u) uf[u].da = bus(uf[u].da); return uf[u].da; } void unir(int u,int v) { u = bus(u); v = bus(v); if (u != v) { if (uf[u].ran > uf[v].ran) uf[v].da = u; else if (uf[u].ran < uf[v].ran) uf[u].da = v; else { uf[u].ran++; uf[v].da = u; } } return; } int construct(std::vector<std::vector<int>> _p) { n = _p.size(); for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); answer.push_back(row); } for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j] = _p[i][j]; for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j] > 2) return 0; for (int i=0;i<n;i++) { uf[i].ran = 0; uf[i].da = i; } for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]>0) unir(i,j); for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j] == 0) if (bus(i) == bus(j)) { return 0; } for (int i=0;i<n;i++) g[bus(i)].push_back(i); for (int i=0;i<n;i++) { for (int j=0;j<(int)g[i].size();j++) act[g[i][j]] = true; for (int j=0;j<(int)g[i].size();j++) { int x = g[i][j]; for (int k=0;k<(int)g[i].size() && act[x];k++) { int y = g[i][k]; if (x != y) { if (a[x][y] == 1) { if (act[y]) { act[x] = false; dad[x] = y; } else if (dad[y] != x) { dad[x] = dad[y]; act[x] = false; } } } } } vector<int> gg; for (int j=0;j<(int)g[i].size();j++) if (act[g[i][j]]) gg.push_back(g[i][j]); for (int j=1;j<(int)gg.size();j++) { answer[gg[j]][gg[j-1]] = answer[gg[j-1]][gg[j]] = 1; } int pp = gg.size(); if (pp>1) answer[gg[0]][gg[pp-1]] = answer[gg[pp-1]][gg[0]] = 1; for (int j=0;j<(int)g[i].size();j++) if (!act[g[i][j]]) { int x = g[i][j]; answer[x][dad[x]] = answer[dad[x]][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...