Submission #1051029

#TimeUsernameProblemLanguageResultExecution timeMemory
1051029sofijavelkovskaStranded Far From Home (BOI22_island)C++14
0 / 100
307 ms48316 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=2e5, INF=2e9; int n, m; int a[MAXN]; vector<int> adj[MAXN]; int link[MAXN], csize[MAXN], cindex[MAXN]; long long sum[MAXN]; set<pair<int, int> > neighbours[MAXN]; bool compare(int x, int y) { return a[x]<a[y]; } int find(int x) { if (x==link[x]) return x; return link[x]=find(link[x]); } void unite(int x, int y, int maxvalue) { x=find(x); y=find(y); if (neighbours[cindex[x]].size()<neighbours[cindex[y]].size()) swap(x, y); for (auto t : neighbours[cindex[y]]) if (t.first>maxvalue) neighbours[cindex[x]].insert(t); neighbours[cindex[y]].clear(); cindex[y]=cindex[x]; if (csize[x]<csize[y]) swap(x, y); csize[x]=csize[x]+csize[y]; sum[x]=sum[x]+sum[y]; link[y]=x; return; } int main() { //ios_base::sync_with_stdio(0); //cin.tie(0); cin >> n >> m; for (int i=0; i<n; i++) cin >> a[i]; for (int i=0; i<m; i++) { int x, y; cin >> x >> y; adj[x-1].push_back(y-1); adj[y-1].push_back(x-1); } int sorted[n]; for (int i=0; i<n; i++) sorted[i]=i; sort(sorted, sorted+n, compare); for (int i=0; i<n; i++) { link[i]=i; csize[i]=1; sum[i]=a[i]; cindex[i]=i; for (auto x : adj[i]) neighbours[i].insert({a[x], x}); } bool possible[n]; for (int i=0; i<n; i++) possible[i]=true; queue<int> q; for (int i=0; i<n; i++) { int x=sorted[i]; for (auto y : adj[x]) if (a[y]<=a[x] && find(x)!=find(y)) unite(x, y, a[x]); int leader=find(x); while (!neighbours[cindex[leader]].empty() && (*neighbours[cindex[leader]].begin()).first<a[x]) neighbours[cindex[leader]].erase(neighbours[cindex[leader]].begin()); if (neighbours[cindex[leader]].empty()) continue; auto it=neighbours[cindex[leader]].begin(); if (sum[leader]>=(*it).first) continue; possible[x]=false; q.push(x); while (!q.empty()) { int y=q.front(); q.pop(); for (auto t : adj[y]) if (a[t]<=a[x] && possible[t]) { possible[t]=false; q.push(t); } } } for (int i=0; i<n; i++) cout << possible[i]; 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...