#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int s[200005];
vector<int> G[200005];
bool ok[200005];
int t[200005],sum[200005];
vector<int> l[200005];
int p[200005];
int reprezentant(int nod)
{
if(t[nod]==nod)
{
return t[nod];
}
return t[nod] = reprezentant(t[nod]);
}
void uneste(int x, int y)
{
x = reprezentant(x);
y = reprezentant(y);
if(x==y)
{
return;
}
if(l[x].size() > l[y].size())
{
t[y] = x;
sum[x] += sum[y];
for(auto it : l[y])
{
l[x].push_back(it);
}
}
else
{
t[x] = y;
sum[y] += sum[x];
for(auto it : l[x])
{
l[y].push_back(it);
}
}
}
bool cmp(int a, int b)
{
return s[a] < s[b];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif // home
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>s[i];
p[i] = i;
}
for(int i=1; i<=m; i++)
{
int x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1; i<=n; i++)
{
t[i] = i;
l[i].push_back(i);
sum[i] = s[i];
ok[i] = true;
}
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++)
{
int nod = p[i];
for(auto it : G[nod])
{
if(s[it] > s[nod])
{
continue;
}
if(sum[reprezentant(it)] >= s[nod])
{
uneste(nod,it);
}
else
{
for(auto e : l[reprezentant(it)])
{
ok[e] = false;
}
}
l[reprezentant(it)].clear();
sum[reprezentant(it)] = 0;
}
}
for(int i=1; i<=n; i++)
{
cout<<ok[i];
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Incorrect |
6 ms |
9836 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Incorrect |
139 ms |
29708 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Incorrect |
206 ms |
28704 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Incorrect |
230 ms |
29624 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
7 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Incorrect |
6 ms |
9836 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |