제출 #431126

#제출 시각아이디문제언어결과실행 시간메모리
431126saleh슈퍼트리 잇기 (IOI20_supertrees)C++17
0 / 100
1 ms332 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 1000 + 23; vector<int> v[MAXN], v2[MAXN]; set<int> r, r2; int n, num1[MAXN], num2[MAXN];// par[MAXN], bitset<MAXN> b2[MAXN]; int construct(vector<vector<int>> p) { n = p.size(); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (p[i][j] == 3) return 0; for (int i = 0; i < n; i++) r.insert(i), v[i].push_back(i); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (p[i][j] == 1) num1[i]++; for (int i = 0; i < n; i++) if (r.find(i) != r.end()) for (int j = i + 1; j < n; j++) if (r.find(j) != r.end()) if (p[i][j] == 1) { while (v[j].size()) { // par[v[j].back()] = i; v[i].push_back(v[j].back()); v[j].pop_back(); } r.erase(j); } vector<vector<int>> ans; for (int i = 0; i < n; i++) { vector<int> row; row.resize(n); ans.push_back(row); } for (auto i : r) r2.insert(i), v2[i].push_back(i); for (auto i : r) { for (auto j : v[i]) for (auto k : v[i]) if (p[k][j] != 1) return 0; for (auto j : v[i]) if (num1[j] != (int)v[i].size()) return 0; for (int j = 1; j < (int)v[i].size(); j++) ans[v[i][j - 1]][v[i][j]] = ans[v[i][j]][v[i][j - 1]] = 1; } for (auto i : r) for (auto j : r) if (i < j) { int tmp = 0; for (auto a : v[i]) for (auto b : v[j]) tmp |= (1 << p[a][b]); if (tmp == 5) return 0; if (tmp == 4) b2[i][j] = b2[j][i] = true; num2[i]++; num2[j]++; } for (auto i : r) if (r2.find(i) != r2.end()) for (auto j : r) if (i < j && r2.find(j) != r2.end()) if (b2[i][j]) { while (v2[j].size()) { v2[i].push_back(v2[j].back()); v2[j].pop_back(); } r2.erase(j); } for (auto i : r2) { for (auto j : v2[i]) for (auto k : v2[i]) if (j != k && !b2[k][j]) return 0; for (auto j : v2[i]) if (num2[j] != (int)v2[i].size() - 1) return 0; for (int j = 1; j < (int)v2[i].size(); j++) ans[v2[i][j - 1]][v2[i][j]] = ans[v2[i][j]][v2[i][j - 1]] = 1; ans[v2[i][v2[i].size() - 1]][v2[i][0]] = ans[v2[i][0]][v2[i][v2[i].size() - 1]] = 1; } // for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (ans[i][j] == true) cout << i << ' ' << j << endl; build(ans); return 1; } //int main() {cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 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...