oj.uz

Submission #710918

# Submission time Handle Problem Language Result Execution time Memory
710918 2023-03-16T05:17:41 Z emptypringlescan Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 35852 KB 
#include <bits/stdc++.h>
using namespace std;
int par[200005];
long long men[200005];
vector<int> sz[200005];
int find(int x){
	if(par[x]==x) return x;
	return par[x]=find(par[x]);
}
void merge(int x, int y){
	x=find(x); y=find(y);
	if(sz[x].size()<=sz[y].size()){
		for(int i:sz[x]) sz[y].push_back(i);
		sz[x].clear();
	}
	else{
		for(int i:sz[y]) sz[x].push_back(i);
		swap(sz[x],sz[y]);
		sz[x].clear();
	}
	men[y]+=men[x];
	men[x]=0;
	par[x]=y;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	for(int i=0; i<200005; i++) par[i]=i;
	int n,m;
	cin >> n >> m;
	pair<long long,int> arr[n];
	for(int i=0; i<n; i++){
		cin >> arr[i].first;
		arr[i].second=i;
	}
	sort(arr,arr+n);
	vector<int> adj[n];
	for(int i=0; i<m; i++){
		int a,b;
		cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int ans[n],on[n];
	for(int i=0; i<n; i++){
		ans[i]=1;
		on[i]=0;
	}
	for(int k=0; k<n; k++){
		int nd=arr[k].second;
		on[nd]=1;
		men[nd]=arr[k].first;
		sz[nd].push_back(nd);
		for(int i:adj[nd]){
			if(!on[i]) continue;
			if((int)men[find(i)]<arr[k].first){
				for(int j:sz[find(i)]) ans[j]=0;
			}
			merge(nd,i);
		}
	}
	for(int i=0; i<n; i++) cout << ans[i];
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Execution timed out 1082 ms 24356 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Incorrect 269 ms 35852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Incorrect 332 ms 32720 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 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Incorrect 5 ms 5972 KB Output isn't correct
5 Halted 0 ms 0 KB -