# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1050857 | sofijavelkovska | Stranded Far From Home (BOI22_island) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN=300000;
// 2e5 ??
int n, m;
int a[MAXN];
vector<int> adj[MAXN];
int link[MAXN], size[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 (link[x]==x)
return x;
return link[x]=find(link[x]);
}
void unite(int x, int y)
{
int xt=x, yt=y;
x=find(x);
y=find(y);
if (size[x]<size[y])
swap(x, y);
size[x]=size[x]+size[y];
sum[x]=sum[x]+sum[y];
link[y]=x;
if (neighbours[cindex[x]].size()<neighbours[cindex[y]].size())
{
for (auto t : neighbours[cindex[x]])
neighbours[cindex[y]].insert(t);
neighbours[cindex[y]].erase({a[xt], xt});
neighbours[cindex[y]].erase({a[yt], yt});
neighbours[cindex[x]].clear();
cindex[x]=cindex[y];
}
else
{
for (auto t : neighbours[cindex[y]])
neighbours[cindex[x]].insert(t);
neighbours[cindex[x]].erase({a[xt], xt});
neighbours[cindex[x]].erase({a[yt], yt});
neighbours[cindex[y]].clear();
cindex[y]=cindex[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;
size[i]=1;
sum[i]=a[i];
for (auto x : adj[i])
neighbours[i].insert({a[x], x});
cindex[i]=i;
}
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);
int leader=find(x);
if (neighbours[cindex[leader]].empty())
continue;
auto it=neighbours[cindex[leader]].begin();
//cout << "x " << x << '\n';
//cout << "sum max " << sum[leader] << ' ' << (*it).first << '\n';
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;
}