oj.uz

Submission #953493

# Submission time Handle Problem Language Result Execution time Memory
953493 2024-03-26T03:30:48 Z PM1 Stranded Far From Home (BOI22_island) C++17
0 / 100
 128 ms 27796 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=2e5+5;
int n,m,par[mxn],s[mxn],root[mxn],sz[mxn],a[mxn];
vector<int>v[mxn],t,g[mxn];
bool ans[mxn];
bool cmp(int x,int y){
	return (s[x]!=s[y])?s[x]<s[y]:x<y;
}
int fndpar(int x){
	return (par[x]==x)?x:par[x]=fndpar(par[x]);
}
void dfs(int z){
	ans[z]=1;
	//cout<<z<<" ";
	for(auto i:g[z]){
		if(s[i]>=a[z])
			dfs(i);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=a[i];
		t.push_back(i);
		par[i]=i;
		root[i]=i;
		sz[i]=1;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(s[x]>s[y] || (s[x]==s[y] && y<x))
			v[x].push_back(y);
		else 
			v[y].push_back(x);
	}
	sort(t.begin(),t.end(),cmp);
	for(auto i:t){
		//cout<<i<<'\n';
		for(auto j:v[i]){
			int x=fndpar(j),y=fndpar(i);
			if(root[x]!=i){
				//cout<<root[x]<<" ";
				s[i]+=s[root[x]];
				g[i].push_back(root[x]);
				if(sz[x]>sz[y])swap(x,y);
				par[x]=y;
				sz[y]+=sz[x];
				root[y]=i;
			}
		}
		//cout<<'\n';
	}
	// /return 0;
	dfs(t.back());
	for(int i=1;i<=n;i++)
		cout<<ans[i];
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Incorrect 93 ms 27796 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Incorrect 128 ms 27352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Incorrect 125 ms 26996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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