제출 #714682

#제출 시각아이디문제언어결과실행 시간메모리
714682ismayilStranded Far From Home (BOI22_island)C++17
20 / 100
1084 ms351392 KiB
#include <bits/stdc++.h> #define int long long //#define endl '\n' using namespace std; const int MAX = 2e5 + 5; vector<int> adj[MAX]; int subtree[MAX], sum[MAX]; int s[MAX], ans[MAX], color[MAX]; void dfs_subtree(int u, int p){ subtree[u] = s[u]; for(auto v : adj[u]){ if(v == p) continue; dfs_subtree(v, u); subtree[u] += subtree[v]; } } void dfs(int u, int p){ for(auto v : adj[u]){ if(v == p) continue; if(subtree[v] < s[u]) continue; ans[v] = 1; dfs(v, u); } } bool bfs(int st){ priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; q.push(make_pair(s[st], st)); while (!q.empty()) { int u = q.top().second; int w = q.top().first; q.pop(); color[u] = 1; if(w > sum[st] && st != u) return false; sum[st] += w; for(auto v : adj[u]){ if(!color[v]) q.push({s[v], v}); } } return true; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; 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; adj[u].push_back(v); adj[v].push_back(u); } if(n <= 2000){ for(int i = 1; i <= n; i++){ memset(color, 0, sizeof(color)); cout<<bfs(i); } cout<<endl; return 0; } dfs_subtree(1, 0); dfs(1, 0); ans[1] = 1; for(int i = 1; i <= n; i++){ cout<<ans[i]; } cout<<endl; }
#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...