Submission #753879

#TimeUsernameProblemLanguageResultExecution timeMemory
753879jakobrsStranded Far From Home (BOI22_island)C++17
20 / 100
253 ms25832 KiB
#include <iostream> #include <queue> #include <tuple> #include <utility> #include <vector> using i64 = int64_t; int main() { std::cin.tie(nullptr)->sync_with_stdio(false); i64 n, m; std::cin >> n >> m; std::vector<i64> a(n); for (i64 i = 0; i < n; i++) std::cin >> a[i]; std::vector<std::vector<i64>> adj(n); std::vector<std::vector<i64>> children(n); for (i64 i = 0; i < m; i++) { i64 u, v; std::cin >> u >> v; u--, v--; adj[u].push_back(v); adj[v].push_back(u); children[std::min(u, v)].push_back(std::max(u, v)); } if (n <= 2000 && m <= 2000) { std::string result; result.reserve(n); std::vector<i64> visited(n); for (i64 i = 0; i < n; i++) { struct Node { i64 size; i64 idx; bool operator<(const Node &rhs) const { return std::tie(rhs.size, idx) < std::tie(size, rhs.idx); } }; std::priority_queue<Node> q; std::fill(visited.begin(), visited.end(), false); visited[i] = true; i64 mass = a[i]; q.push(Node{.size = 0, .idx = i}); while (!q.empty()) { Node node = q.top(); if (node.size > mass) break; mass += node.size; q.pop(); for (i64 j : adj[node.idx]) { if (!visited[j]) { visited[j] = true; q.push(Node{.size = a[j], .idx = j}); } } } result.push_back(q.empty() ? '1' : '0'); } std::cout << result; } else { std::string result(n, '0'); std::vector<i64> sizes(n); for (i64 i = n - 1; i >= 0; i--) { sizes[i] = a[i]; for (i64 j : children[i]) { sizes[i] += sizes[j]; } } result[0] = '1'; for (i64 i = 0; i < n; i++) { if (result[i] == '1') { for (i64 j : children[i]) { if (sizes[j] >= a[i]) { result[j] = '1'; } } } } std::cout << result; } }
#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...