oj.uz

Submission #710930

# Submission time Handle Problem Language Result Execution time Memory
710930 2023-03-16T05:33:11 Z emptypringlescan Stranded Far From Home (BOI22_island) C++17
25 / 100
 266 ms 70180 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);
	assert(x<200005&&y<200005);
	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(i,nd);
		}
	}
	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 6484 KB Output is correct
3 Correct 3 ms 6564 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 3 ms 6588 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 165 ms 34396 KB Output is correct
4 Correct 170 ms 35420 KB Output is correct
5 Correct 226 ms 36360 KB Output is correct
6 Correct 228 ms 37648 KB Output is correct
7 Correct 198 ms 37464 KB Output is correct
8 Correct 162 ms 34220 KB Output is correct
9 Correct 191 ms 40948 KB Output is correct
10 Correct 158 ms 33368 KB Output is correct
11 Correct 142 ms 34916 KB Output is correct
12 Correct 177 ms 34668 KB Output is correct
13 Correct 128 ms 35936 KB Output is correct
14 Correct 144 ms 35700 KB Output is correct
15 Correct 140 ms 33336 KB Output is correct
16 Correct 88 ms 33080 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 254 ms 38136 KB Output is correct
3 Correct 251 ms 38408 KB Output is correct
4 Correct 155 ms 33472 KB Output is correct
5 Correct 152 ms 34168 KB Output is correct
6 Correct 243 ms 38132 KB Output is correct
7 Correct 151 ms 33312 KB Output is correct
8 Correct 142 ms 33312 KB Output is correct
9 Correct 90 ms 33176 KB Output is correct
10 Correct 141 ms 33892 KB Output is correct
11 Correct 162 ms 34244 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 266 ms 36340 KB Output is correct
3 Runtime error 248 ms 70180 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 6484 KB Output is correct
3 Correct 3 ms 6564 KB Output is correct
4 Incorrect 5 ms 6740 KB Output isn't correct
5 Halted 0 ms 0 KB -