제출 #713395

#제출 시각아이디문제언어결과실행 시간메모리
713395garyye슈퍼트리 잇기 (IOI20_supertrees)C++17
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> #include "supertrees.h" using namespace std; template<class T> bool cmin(T& a, T b) { if(a > b) { a = b; return true; } return false; } template<class T> bool cmax(T& a, T b) { if(a < b) { a = b; return true; } return false; } typedef pair<int, int> pii; #define SZ(x) ((int) (x.size())) #define fi first #define se second const int N = 2222; int n; int vis[N]; int root[N]; vector<vector<int>> p, b; vector<int> roots, t; void add(int u, int v) { b[u][v] = b[v][u] = 1; } void dfs(int u) { t.push_back(u); vis[u] = 1; for(int v = 0; v < n; ++v) { if(u == v || vis[v] || p[u][v] != 1) continue; dfs(v); } } void rec(int u) { vis[u] = true; t.push_back(u); for(int v: roots) { if(p[u][v] == 2 && !vis[v]) { rec(v); } } } int construct(vector<vector<int>> _p) { p = _p; n = p.size(); b = vector<vector<int>>(n, vector<int>(n, 0)); // Last subtask for(auto& a: p) for(auto& b: a) if(b == 3) return 0; for(int foo = 0; foo < n; foo++) { if(vis[foo]) continue; t.clear(); dfs(foo); for(int i: t) { for(int j = 0; j < n; ++j) { if(p[i][j] != p[t[0]][j]) { return 0; } } } // Can name anyone the root since they all the same for(int i = 0; i + 1 < SZ(t); ++i) { add(t[i], t[i + 1]); root[t[i + 1]] = t[0]; } roots.push_back(t[0]); } printf("Roots=%d\n", SZ(roots)); memset(vis, 0, sizeof vis); for(int u: roots) { if(vis[u]) continue; t.clear(); rec(u); if(SZ(t) == 2) return 0; if(SZ(t) == 1) continue; for(int x: t) for(int y: t) if(x != y && p[x][y] != 2) return 0; for(int i = 0; i < SZ(t); ++i) { add(t[i], t[(i+1)%SZ(t)]); } } build(b); 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...