Submission #1092969

#TimeUsernameProblemLanguageResultExecution timeMemory
1092969duckindogStranded Far From Home (BOI22_island)C++17
20 / 100
200 ms31056 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200'000 + 10; int n, m; int s[N]; vector<int> ad[N]; namespace sub1 { static const int SZ = 2000 + 10; bool f[SZ]; void solve() { for (int i = 1; i <= n; ++i) { using pii = pair<int, int>; priority_queue<pii, vector<pii>, greater<>> q; for (const auto& v : ad[i]) q.push({s[v], v}); memset(f, false, sizeof f); long long total = s[i]; f[i] = true; while (q.size()) { auto [cnt, u] = q.top(); q.pop(); if (f[u] || total < cnt) continue; total += cnt; f[u] = true; for (const auto& v : ad[u]) if (!f[v]) q.push({s[v], v}); } cout << *min_element(f + 1, f + n + 1); } cout << "\n"; } } namespace sub2 { long long d[N]; void dfs0(int u, int p = -1) { d[u] = s[u]; for (const auto& v : ad[u]) { if (v == p) continue; dfs0(v, u); d[u] += d[v]; } } bool f[N]; void dfs1(int u, int p = -1) { for (const auto& v : ad[u]) { if (v == p) continue; if (d[v] >= s[u]) f[v] |= f[u]; dfs1(v, u); } } void solve() { dfs0(1); dfs1(f[1] = 1); for (int i = 1; i <= n; ++i) cout << f[i]; cout << "\n"; } } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> s[i]; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; ad[u].push_back(v); ad[v].push_back(u); } if (n <= 2000 && m <= 2000) { sub1::solve(); return 0; } bool sub2 = (m == n - 1); for (int i = 1; i < n; ++i) sub2 &= (s[i] >= s[i + 1]); if (sub2) { sub2::solve(); return 0; } }
#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...