oj.uz

Submission #919083

# Submission time Handle Problem Language Result Execution time Memory
919083 2024-01-31T08:21:06 Z Isam Stranded Far From Home (BOI22_island) C++17
0 / 100
 89 ms 17344 KB 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
const int sz=200005;

int n, m, sizel[sz], fa[sz];
int folk[sz], sm[sz];

bool ans[sz];

inline void init(){
	for(int i=1; i<=n; ++i) sizel[i]=1, fa[i]=i, ans[i]=true;
	return;
}
int find_set(int &v){
    if(fa[v] == v)
        return v;
       if(!ans[fa[v]]) ans[v]=0;
    return fa[v]=find_set(fa[v]);
}


	

//b->a

bool Union(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a ^ b){
        if(folk[a]<folk[b]) swap(a,b);
        if(folk[a]>sm[b]) ans[b]=0;
        fa[b]=a;
        sm[a]+=sm[b];
        
        return true;
    }
    return false;
}

struct edge{
	int a, b;
	int maxf;
	
	
	
};

bool cmp(edge e1, edge e2){
	return e1.maxf<e2.maxf;
}



vector<edge> e;

int a, b, maxf;

inline void Solution(){
	cin>>n>>m;
	init();
	for(int i=1; i<=n; ++i){
		cin>>folk[i];
		sm[i]=folk[i];
	}
	
	
	for(int i=1; i<=m; ++i){
		cin>>a>>b;
		e.emplace_back((edge){a,b,max(folk[a], folk[b])});
	}
	sort(e.begin(), e.end(), cmp);
	
	for(int i=0; i<m; ++i){
		Union(e[i].a, e[i].b);
		
	}
	
	for(int i=1; i<=n; ++i) cout<<ans[i];
	
	
	return;
	
}
signed main(){
    ios_base::sync_with_stdio(false);
    Solution();
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Incorrect 2 ms 6744 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 79 ms 14532 KB Output is correct
4 Incorrect 65 ms 17344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Incorrect 89 ms 14016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 78 ms 14576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Incorrect 2 ms 6744 KB Output isn't correct
6 Halted 0 ms 0 KB -