oj.uz

Submission #711682

# Submission time Handle Problem Language Result Execution time Memory
711682 2023-03-17T11:07:58 Z hpesoj Stranded Far From Home (BOI22_island) C++17
10 / 100
 717 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], sz[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(sz[rootx] < sz[rooty]) swap(rootx, rooty), swap(nodes[rootx], nodes[rooty]);
	root[rooty] = rootx, sz[rootx] += sz[rooty], val[rootx] += val[rooty];
	for(auto it = nodes[rooty].begin(); it != nodes[rooty].end(); it++) nodes[rootx].pb(*it);
	//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, 1);
	for(int i = 1; i <= n; i++){
		cin >> s[i].fi;
		s[i].se = i, root[i] = i, val[i] = s[i].fi, sz[i] = 1;
		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]){
				mark(k);
			}
			merge(s[i].se, k);
		}
	}
	for(int i = 1; i <= n; i++) cout << ans[i];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 12 ms 16340 KB Output is correct
5 Correct 9 ms 11732 KB Output is correct
6 Correct 11 ms 15880 KB Output is correct
7 Correct 11 ms 16212 KB Output is correct
8 Correct 11 ms 15188 KB Output is correct
9 Correct 21 ms 30052 KB Output is correct
10 Correct 7 ms 10212 KB Output is correct
11 Correct 6 ms 10204 KB Output is correct
12 Correct 6 ms 10116 KB Output is correct
13 Correct 22 ms 29404 KB Output is correct
14 Correct 8 ms 11604 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 6 ms 9684 KB Output is correct
3 Runtime error 494 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 349 ms 75548 KB Output is correct
3 Correct 316 ms 78004 KB Output is correct
4 Runtime error 476 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 5 ms 9684 KB Output is correct
2 Runtime error 717 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 5 ms 9708 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 12 ms 16340 KB Output is correct
5 Correct 9 ms 11732 KB Output is correct
6 Correct 11 ms 15880 KB Output is correct
7 Correct 11 ms 16212 KB Output is correct
8 Correct 11 ms 15188 KB Output is correct
9 Correct 21 ms 30052 KB Output is correct
10 Correct 7 ms 10212 KB Output is correct
11 Correct 6 ms 10204 KB Output is correct
12 Correct 6 ms 10116 KB Output is correct
13 Correct 22 ms 29404 KB Output is correct
14 Correct 8 ms 11604 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Runtime error 494 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -