Submission #593624

#TimeUsernameProblemLanguageResultExecution timeMemory
593624BlagojceStranded Far From Home (BOI22_island)C++11
10 / 100
1074 ms443620 KiB
#include <bits/stdc++.h> #define fr(i, n, m) for(int i = (n); i < (m); i ++) #define st first #define nd second #define pb push_back #define pq priority_queue #define all(x) begin(x), end(x) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int mxn = 2e5 + 5; int n, m; vector<int> g[mxn]; ll a[mxn]; vector<int> S[mxn]; vector<int> G[mxn]; ll sum[mxn]; int v_count = 0; int vis_ver[mxn]; int vis_edg[mxn]; vector<int> merge(int u, int v){ vector<int> cand; for(auto vp : S[v]){ if(vis_ver[vp] == v_count) continue; S[u].pb(vp); sum[u] += a[vp]; vis_ver[vp] = v_count; } for(auto ep : G[v]){ if(vis_edg[ep] == v_count || vis_ver[ep] == v_count) continue; G[u].pb(ep); cand.pb(ep); vis_edg[ep] = v_count; } return cand; } void expand(int u){ ++v_count; for(auto e : S[u]) vis_ver[e] = v_count; for(auto e : G[u]) vis_edg[e] = v_count; pq <pair<int,int> > Q; for(auto e : G[u]) Q.push({-a[e], e}); while(!Q.empty()){ int c = Q.top().nd; Q.pop(); if(vis_ver[c] == v_count) continue; if(sum[u] < a[c]) continue; vector<int> cand = merge(u, c); for(auto c : cand){ Q.push({-a[c], c}); } } sort(all(G[u])); G[u].erase(unique(all(G[u])),G[u].end()); } int main(){ cin >> n >> m; fr(i, 0, n){ cin >> a[i]; } fr(i, 0, m){ int u, v; cin >> u >> v; --u, --v; g[u].pb(v); g[v].pb(u); } fr(i, 0, n){ G[i] = g[i]; S[i] = {i}; sum[i] = a[i]; } fr(i, 0, n){ expand(i); } fr(i, 0, n){ if((int)S[i].size() == n) cout<<1; else cout<<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...