제출 #1196146

#제출 시각아이디문제언어결과실행 시간메모리
1196146noabenysraelConnecting Supertrees (IOI20_supertrees)C++20
56 / 100
119 ms22260 KiB
#include <vector> #include <iostream> #include <set> #include "supertrees.h" using namespace std; using ll = int; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using pll = pair<int, int>; using vb = vector<bool>; using vpll = vector <pll>; vvll partition(vll &nums, vvll &p, ll u_bound, ll l_bound) { vvll part; ll n = nums.size(); vb vis(n, 0); for (ll i = 0; i < n; i++) { if (vis[i]) continue; part.push_back({ nums[i] }); vis[i] = 1; for (ll j = i + 1; j < n; j++) { if (p[nums[i]][nums[j]] >= l_bound && p[nums[i]][nums[j]] <= u_bound) { vis[j] = true; part.back().push_back(nums[j]); } } } return part; } int construct(std::vector<std::vector<int>> p) { ll n = p.size(); for (ll i = 0; i < n; i++) { if (p[i][i] != 1) return 0; } for (ll i = 0; i < n; i++) { for (ll j = i + 1; j < n; j++) { if (p[i][j] != p[j][i]) return 0; if (p[i][j] == 3) return 0; } } vll nums(n); for (ll i = 0; i < n; i++) nums[i] = i; vvll part1 = partition(nums, p, 2, 1); vvvll part; for (vll& v : part1) { part.push_back(partition(v, p, 1, 1)); } vpll locs(n); for (ll comp = 0; comp < part.size(); comp++) { for (ll tree = 0; tree < part[comp].size(); tree++) { for (ll v : part[comp][tree]) { locs[v] = { comp, tree }; } } } for (ll i = 0; i < n; i++) { for (ll j = i + 1; j < n; j++) { if (locs[i].first != locs[j].first) { if (p[i][j] != 0) return 0; } else if (locs[i].second == locs[j].second) { if (p[i][j] != 1) return 0; } else if (p[i][j] != 2) return 0; } } vvll b(n, vll(n, 0)); for (vvll& comp : part) { for (vll& tree : comp) { for (ll i = 1; i < tree.size(); i++) { b[tree[i]][tree[0]] = 1; b[tree[0]][tree[i]] = 1; } } if (comp.size() > 1) { for (ll i = 0; i < comp.size(); i++) { b[comp[i][0]][comp[(i + 1) % comp.size()][0]] = 1; b[comp[(i + 1) % comp.size()][0]][comp[i][0]] = 1; } } } 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...