#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int stala=2e5+10;
long long war[stala];
int ojciec[stala];
int wys[stala];
int reprezentant[stala];
long long suma[stala];
set<pair<long long,pair<int,int> > >secik; //mniejsza wartosc/wieksza wartosc
vector<int>wektor[stala];
vector<int>w[stala];//0 - zablokowana/1 - wolna
bool o[stala];
int korzen=0;
int Find(int a){
if(ojciec[a]!=a){
return Find(ojciec[a]);
}
else{
return a;
}
}
void Union(int a,int b){
int do_wstawienia;
a=Find(a);
b=Find(b);
if(war[reprezentant[a]]>war[reprezentant[b]]){
wektor[reprezentant[a]].push_back(reprezentant[b]);
do_wstawienia=reprezentant[a];
if(suma[b]>=war[reprezentant[a]]){
w[reprezentant[a]].push_back(1);
}
else{
w[reprezentant[a]].push_back(0);
}
}
else{
wektor[reprezentant[b]].push_back(reprezentant[a]);
do_wstawienia=reprezentant[b];
if(suma[a]>=war[reprezentant[b]]){
w[reprezentant[b]].push_back(1);
}
else{
w[reprezentant[b]].push_back(0);
}
}
if(wys[a]<wys[b]){
ojciec[a]=b;
wys[b]=max(wys[b],wys[a]+1);
suma[b]+=suma[a];
reprezentant[b]=do_wstawienia;
}
else{
ojciec[b]=a;
wys[a]=max(wys[a],wys[b]+1);
suma[a]+=suma[b];
reprezentant[a]=do_wstawienia;
}
korzen=do_wstawienia;
}
void dfs(int k){
o[k]=1;
for(int i=0;i<(int)wektor[k].size();i++){
if(w[k][i]==1){
dfs(wektor[k][i]);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int ile,drogi;
cin>>ile>>drogi;
for(int i=1;i<=ile;i++){
cin>>war[i];
}
for(int i=1;i<=ile;i++){
ojciec[i]=i;
wys[i]=1;
reprezentant[i]=i;
suma[i]=war[i];
}
for(int i=1;i<=drogi;i++){
int a,b;//a - wartosc mniejsza/b - wartosc wieksza
cin>>a>>b;
long long pom=max(war[a],war[b]);
if(war[a]>war[b]){
swap(a,b);
}
secik.insert(make_pair(pom,make_pair(a,b)));
}
while(!secik.empty()){
int w1=secik.begin()->second.first;
int w2=secik.begin()->second.second;
if(Find(w1)!=Find(w2)){
Union(w1,w2);
}
secik.erase(secik.begin());
}
dfs(korzen);
for(int i=1;i<=ile;i++){
cout<<o[i];
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9728 KB |
Output is correct |
2 |
Correct |
7 ms |
9732 KB |
Output is correct |
3 |
Incorrect |
7 ms |
9684 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9732 KB |
Output is correct |
2 |
Incorrect |
5 ms |
9652 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
9744 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9728 KB |
Output is correct |
2 |
Correct |
7 ms |
9732 KB |
Output is correct |
3 |
Incorrect |
7 ms |
9684 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |