제출 #406099

#제출 시각아이디문제언어결과실행 시간메모리
406099Falcon슈퍼트리 잇기 (IOI20_supertrees)C++17
96 / 100
288 ms28012 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i = 0; i < (n); ++i) int construct_forest(const vector<vector<int>>& p) { int n{int(p.size())}; vector<bool> vis(n); rep(i, n) if(!vis[i]) rep(j, n) if(p[i][j]) { if(p[i] != p[j]) return 0; vis[j] = true; } return 1; } vector<vector<int>> build_forest(const vector<vector<int>>& p) { int n{int(p.size())}; vector<bool> vis(n); vector<vector<int>> adj(n, vector<int>(n)); rep(i, n) if(!vis[i]) rep(j, n) if(p[i][j] && i != j) adj[i][j] = adj[j][i] = 1, vis[j] = true; return adj; } int add_cycles(const vector<vector<int>>& p, vector<vector<int>>& adj) { int n{int(p.size())}; vector<bool> vis(n); vector<int> tree_head; vector<int> tree_of(n); int t{}; rep(i, n) if(!vis[i]) { tree_head.push_back(i); rep(j, n) if(p[i][j] == 1) tree_of[j] = t, vis[j] = true; ++t; } rep(i, n) rep(j, n) if(p[i][j] == 1) assert(tree_of[i] == tree_of[j]); else assert(tree_of[i] != tree_of[j]); rep(i, n) rep(j, n) if(p[i][j] == 2 && p[tree_head[tree_of[i]]][j] != 2) return 0; else if(p[tree_head[tree_of[i]]][j] == 2 && p[i][j] != 2) return 0; fill(vis.begin(), vis.end(), false); vector<vector<int>> tree_comp; for(int i: tree_head) if(!vis[i]) { tree_comp.emplace_back(); for(int j: tree_head) if(p[i][j] != 0) { rep(k, n) { if(p[i][k] == 2 && p[k][j] == 0) return 0; else if(p[i][k] == 0 && p[k][j] == 2) return 0; vis[j] = true; } tree_comp.back().push_back(j); } } for(vector<int>& comp: tree_comp) { if(int(comp.size()) == 2) return 0; rep(i, int(comp.size())) { int j = comp[(i + 1) % int(comp.size())]; if(comp[i] != j) adj[comp[i]][j] = adj[j][comp[i]] = 1; } } return 1; } int construct(vector<vector<int>> p) { int n{int(p.size())}; vector<vector<int>> p2{p}; rep(i, n) rep(j, n) p2[i][j] %= 2; if(!construct_forest(p2)) return 0; vector<vector<int>> adj{build_forest(p2)}; if(!add_cycles(p, adj)) return 0; build(adj); 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...