Submission #654368

#TimeUsernameProblemLanguageResultExecution timeMemory
654368ertoStranded Far From Home (BOI22_island)C++17
0 / 100
361 ms45136 KiB
#include <bits/stdc++.h> typedef long long int ll; typedef long double ld; #define INF (int)(1e9 + 7) #define INF2 998244353 #define N (ll)(2e5 + 5) //#define f first //#define s second #define int ll #define lsb(x) (x & (-x)) using namespace std; int n, m, g, h; int ans[N]; set<pair<int, int>> v[N]; int a[N]; int p[N], sz[N]; int get(int x){ return (p[x] == x ? x : get(p[x])); } void unite(int x, int y){ int a = get(x), b = get(y); if(a == b)return; if(sz[a] < sz[b])swap(a, b); sz[a] += sz[b]; p[b] = a; } void solve(){ cin >> n >> m; for(int i=1; i<=n; i++){ cin >> a[i]; } for(int i=1; i<=m; i++){ cin >> g >> h; v[g].insert({a[h], h}); v[h].insert({a[g], g}); } priority_queue<pair<int, int>> pq; for(int i=1; i<=n; i++){ pq.push({-a[i], i}); } for(int i=1; i<=n; i++){ sz[i] = a[i]; p[i] = i; } while(!pq.empty()){ auto p = pq.top(); pq.pop(); int i = p.second; bool bb = 1; //cout << i << ' '; for(auto z : v[i]){ int u = z.second; //if(i == 4)cout << u << a[u] << sz[get(i)] << '\n'; if(sz[get(i)] < a[u]){ bb=0; } unite(i, u); } if(bb==0)ans[i] = -1; else{ ans[i] = 1; } } for(int i=1; i<=n; i++){ if(ans[i] == -1)ans[i] = 0; else{ ans[i] = ans[get(i)]; } } for(int i=1; i<=n; i++){ cout << ans[i]; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int T = 1; //cin>>T; for(int i=1; i<=T; i++){ solve(); } }
#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...