oj.uz

Submission #711680

# Submission time Handle Problem Language Result Execution time Memory
711680 2023-03-17T11:05:46 Z hpesoj Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 458100 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];
set <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].insert(*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].insert(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 8 ms 14420 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 85 ms 43164 KB Output is correct
5 Correct 30 ms 22280 KB Output is correct
6 Correct 76 ms 40420 KB Output is correct
7 Correct 83 ms 42072 KB Output is correct
8 Correct 68 ms 37104 KB Output is correct
9 Correct 255 ms 108564 KB Output is correct
10 Correct 11 ms 15704 KB Output is correct
11 Correct 12 ms 15700 KB Output is correct
12 Correct 11 ms 15596 KB Output is correct
13 Correct 238 ms 105408 KB Output is correct
14 Correct 30 ms 22100 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14392 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Execution timed out 1040 ms 413272 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14464 KB Output is correct
2 Correct 902 ms 243820 KB Output is correct
3 Correct 917 ms 252356 KB Output is correct
4 Execution timed out 1085 ms 458100 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Execution timed out 1074 ms 364380 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 85 ms 43164 KB Output is correct
5 Correct 30 ms 22280 KB Output is correct
6 Correct 76 ms 40420 KB Output is correct
7 Correct 83 ms 42072 KB Output is correct
8 Correct 68 ms 37104 KB Output is correct
9 Correct 255 ms 108564 KB Output is correct
10 Correct 11 ms 15704 KB Output is correct
11 Correct 12 ms 15700 KB Output is correct
12 Correct 11 ms 15596 KB Output is correct
13 Correct 238 ms 105408 KB Output is correct
14 Correct 30 ms 22100 KB Output is correct
15 Correct 7 ms 14392 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Execution timed out 1040 ms 413272 KB Time limit exceeded
18 Halted 0 ms 0 KB -