제출 #1200488

#제출 시각아이디문제언어결과실행 시간메모리
1200488AzeTurk810Connecting Supertrees (IOI20_supertrees)C++20
21 / 100
130 ms26060 KiB
#include "supertrees.h" #include <vector> #include <iostream> struct DSU { std::vector<int> par; int n , components; DSU(int _n) { n = _n; components = n; par.assign(n , -1); } int Find(int u) { if(par[u] < 0 ) return u; return par[u] = Find(par[u]); } bool Union(int u , int v) { u = Find(u); v = Find(v); if(u != v) { components--; if(par[u] > par[v]) { par[v] += par[u]; par[u] = v; return true; } par[u] += par[v]; par[v] = u; return true; } else { return false; } } }; std::vector<int> used; std::vector<std::vector<int>> g; std::vector<std::vector<int>> answer; void dfs(int v) { used[v] = true; for(int &to : g[v]) { if(!used[to]) { answer[v][to] = true; answer[to][v] = true; dfs(to); } } } int construct(std::vector<std::vector<int>> p) { int n = p.size(); used.assign(n , false); g.resize(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if(p[i][j] != p[j][i]) return false; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if(p[i][j]) { g[i].push_back(j); } } } answer.assign(n , std::vector<int> (n , false)); for (int i = 0; i < n; i++) { if(!used[i]) { dfs(i); } } DSU t(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if(p[i][j]) t.Union(i , j); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if(!p[i][j]) { // std::cerr << i << ':' << j << std::endl; if(t.Find(i) == t.Find(j)) return false; } } } 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...