Submission #1024911

#TimeUsernameProblemLanguageResultExecution timeMemory
1024911overwatch9Stranded Far From Home (BOI22_island)C++17
10 / 100
756 ms524288 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxn = 2e5 + 1; ll S[maxn]; vector <int> adj[maxn]; bool ans[maxn]; ll sz[maxn]; void dfs(int s, int p) { sz[s] = S[s]; for (auto i : adj[s]) { if (i == p) continue; dfs(i, s); sz[s] += sz[i]; } } vector <int> v; void dfs2(int s, int p) { if (sz[s] >= S[p] && ans[p] == true) ans[s] = true; for (auto i : adj[s]) { if (i == p) continue; dfs2(i, s); } } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> S[i]; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } int root = max_element(S, S + n + 1) - S; dfs(root, root); ans[root] = root; for (auto i : adj[root]) { dfs2(i, root); v.clear(); } for (int i = 1; i <= n; i++) cout << ans[i]; 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...