Submission #995374

#TimeUsernameProblemLanguageResultExecution timeMemory
995374asdfgraceStranded Far From Home (BOI22_island)C++17
20 / 100
206 ms37972 KiB
#include <bits/stdc++.h> using namespace std; #define dbg(x) x #define prt(x) dbg(cerr << x) #define pv(x) prt(#x << " = " << x << '\n') #define parr(x) dbg(prt(#x << " = "); for (auto y : x) prt(y << ' '); prt('\n')); #define parr2d(x) dbg(prt(#x << " = \n"); for (auto y : x) parr(y); prt('\n')); /* which ties are possible? a can convince b if sum(a) > sum(b) note that nodes are weighted note that the tie with the strictly least number can't be 1 in the end one with strictly most can be 1 in the end how to greedily make 1 the largest? dfs from the node and keep adding the smallest adj greedily and make sure that the size of this color's comp is greater than any other color's comp subtask 1: brute force subtask 2: tree; every node's parent has greater value than self you can always get everything in your own subtree go to the root and for every node on the path to the root you also absorb the parent and everything else in the parent's subtree - note that that is guaranteed to be possible if you've already absorbed the parent this dp cond is checkable as you go up the tree (this node's subtree sum >= parent's value?) all the values to the root have to be true for a node to work subtask 3: just some weird stuff with set ig */ int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<long long> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } bool inc = false; for (int i = 0; i < n - 1; i++) { if (s[i + 1] > s[i]) { inc = true; } } vector<vector<int>> edges(n); for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; x--; y--; edges[x].push_back(y); edges[y].push_back(x); } if (n <= 2000 && m <= 2000) { for (int i = 0; i < n; i++) { vector<bool> vis(n, false); vis[i] = true; priority_queue<array<long long, 2>> que; que.push({-s[i], i}); bool ok = true; long long tot = s[i]; while (que.size()) { long long sz = -que.top()[0], node = que.top()[1]; que.pop(); if (sz > tot) { ok = false; break; } if (node != i) { tot += sz; } for (auto next : edges[node]) { if (!vis[next]) { vis[next] = true; que.push({-s[next], next}); } } } cout << (ok ? 1 : 0); } cout << '\n'; } else if (m == n - 1 && !inc) { vector<bool> ok(n, true); vector<long long> sum = s; function<void(int, int)> dfs1 = [&] (int node, int par) { for (auto next : edges[node]) { if (next != par) { dfs1(next, node); sum[node] += sum[next]; } } }; dfs1(0, 0); function<void(int, int)> dfs2 = [&] (int node, int par) { if (node != 0) { ok[node] = ok[par]; if (s[par] > sum[node]) { ok[node] = false; } } for (auto next : edges[node]) { if (next != par) { dfs2(next, node); } } }; dfs2(0, 0); for (int i = 0; i < n; i++) { cout << (ok[i] ? 1 : 0); } cout << '\n'; } }
#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...