oj.uz

Submission #711696

# Submission time Handle Problem Language Result Execution time Memory
711696 2023-03-17T11:17:13 Z hpesoj Stranded Far From Home (BOI22_island) C++17
10 / 100
 713 ms 524288 KB 
#include <bits/stdc++.h>
#define int long long
#define pi pair <int, int>
#define ppi pair <pi, int>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << '\n'
#define debug2(x, y) cout << #x << ": " << x << ' ' << #y << ": " << y << '\n'
#define debug3(x, y, z) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << '\n'
#define debug4(x, y, z, w) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << ' ' << #w << ": " << w << '\n'
using namespace std;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

const int inf = 1000000000000000000, mod = 998244353;
int n, m, root[200005], val[200005];
pi s[200005];
vector <int> nodes[200005];
vector <int> adj[200005];
bool processed[200005], ans[200005];
int getroot(int x){
	if(x == root[x]) return x;
	else return root[x] = getroot(root[x]);
}
void merge(int x, int y){
	int rootx = getroot(x), rooty = getroot(y);
	//debug4(x, rootx, y, rooty);
	if(rootx == rooty) return;
	if(nodes[rootx].size() < nodes[rooty].size()) swap(rootx, rooty), swap(nodes[rootx], nodes[rooty]);
	root[rooty] = rootx, val[rootx] += val[rooty];
	for(auto it = nodes[rooty].begin(); it != nodes[rooty].end(); it++) nodes[rootx].pb(*it);
	nodes[rooty].clear();
	//cout << "merged: " << x << ", " << y << '\n';
}
void mark(int x){
	for(auto it = nodes[x].begin(); it != nodes[x].end(); it++) ans[*it] = 0;
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	fill(ans+1, ans+n+1, 0);
	for(int i = 1; i <= n; i++){
		cin >> s[i].fi;
		s[i].se = i, root[i] = i, val[i] = s[i].fi;
		nodes[i].pb(i);
	}
	for(int i = 1; i <= m; i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	sort(s+1, s+n+1);
	for(int i = 1; i <= n; i++){
		processed[s[i].se] = 1;
		for(int j : adj[s[i].se]){
			//debug3(s[i].se, j, processed[j]);
			if(!processed[j]) continue;
			int k = getroot(j);
			//debug4(s[i].se, s[i].fi, k, val[k]);
			if(s[i].fi > val[k]){
				nodes[k].clear();
			}
			merge(s[i].se, k);
		}
	}
	for(int i = 1; i <= n; i++){
		if(i != getroot(i)) continue;
		for(auto it = nodes[i].begin(); it != nodes[i].end(); it++) ans[*it] = 1;
	}
	for(int i = 1; i <= n; i++) cout << ans[i];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 10 ms 13516 KB Output is correct
5 Correct 7 ms 10836 KB Output is correct
6 Correct 11 ms 15700 KB Output is correct
7 Correct 9 ms 13324 KB Output is correct
8 Correct 9 ms 13012 KB Output is correct
9 Correct 15 ms 20436 KB Output is correct
10 Correct 6 ms 10088 KB Output is correct
11 Correct 6 ms 10068 KB Output is correct
12 Correct 6 ms 10036 KB Output is correct
13 Correct 20 ms 29360 KB Output is correct
14 Correct 7 ms 10324 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Runtime error 537 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 258 ms 52156 KB Output is correct
3 Correct 261 ms 53596 KB Output is correct
4 Runtime error 494 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Runtime error 713 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 10 ms 13516 KB Output is correct
5 Correct 7 ms 10836 KB Output is correct
6 Correct 11 ms 15700 KB Output is correct
7 Correct 9 ms 13324 KB Output is correct
8 Correct 9 ms 13012 KB Output is correct
9 Correct 15 ms 20436 KB Output is correct
10 Correct 6 ms 10088 KB Output is correct
11 Correct 6 ms 10068 KB Output is correct
12 Correct 6 ms 10036 KB Output is correct
13 Correct 20 ms 29360 KB Output is correct
14 Correct 7 ms 10324 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 7 ms 9684 KB Output is correct
17 Runtime error 537 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -