oj.uz

Submission #710924

# Submission time Handle Problem Language Result Execution time Memory
710924 2023-03-16T05:25:26 Z emptypringlescan Stranded Far From Home (BOI22_island) C++17
25 / 100
 323 ms 70268 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
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;
}
int32_t 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;
				sz[find(i)].clear();
			}
			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 4 ms 6484 KB Output is correct
2 Correct 4 ms 6584 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Incorrect 5 ms 6740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 173 ms 34408 KB Output is correct
4 Correct 174 ms 34224 KB Output is correct
5 Correct 265 ms 36324 KB Output is correct
6 Correct 251 ms 37572 KB Output is correct
7 Correct 233 ms 37468 KB Output is correct
8 Correct 156 ms 34276 KB Output is correct
9 Correct 196 ms 40872 KB Output is correct
10 Correct 167 ms 33332 KB Output is correct
11 Correct 141 ms 34872 KB Output is correct
12 Correct 182 ms 34540 KB Output is correct
13 Correct 152 ms 33332 KB Output is correct
14 Correct 165 ms 33308 KB Output is correct
15 Correct 135 ms 33372 KB Output is correct
16 Correct 94 ms 33064 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 280 ms 38064 KB Output is correct
3 Correct 268 ms 38352 KB Output is correct
4 Correct 163 ms 33344 KB Output is correct
5 Correct 142 ms 33388 KB Output is correct
6 Correct 291 ms 38236 KB Output is correct
7 Correct 174 ms 33372 KB Output is correct
8 Correct 176 ms 33372 KB Output is correct
9 Correct 100 ms 33020 KB Output is correct
10 Correct 160 ms 33204 KB Output is correct
11 Correct 177 ms 34088 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 323 ms 36176 KB Output is correct
3 Runtime error 260 ms 70268 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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