oj.uz

Submission #711158

# Submission time Handle Problem Language Result Execution time Memory
711158 2023-03-16T08:59:16 Z YeoBL Stranded Far From Home (BOI22_island) C++14
50 / 100
 1000 ms 39052 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
const int MAX_N = 2e5 + 5;
bool active[MAX_N], ans[MAX_N];
int siz[MAX_N], par[MAX_N], s[MAX_N], powe[MAX_N], requ[MAX_N];
void init(int x){
	for (int i = 0; i < x; i++){
		par[i] = i;
		siz[i] = s[i];
	}
}
int head(int x){
	if (par[x] == x) return x;
	return par[x] = head(par[x]);
}
void merge(int a, int b){
	int pa = head(a), pb = head(b);
	if (pa == pb) return;
	par[pa] = pb;
	siz[pb] += siz[pa];
}
int stronk(int a){
	return siz[head(a)];
}
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m, x, y; cin >> n >> m; 
	fill(requ, requ + n, 1e9);
	vector <int> edg[n];
	bool st2 = true;
	for (int i = 0; i < n; i++){
		cin >> s[i];
		if (i and s[i] > s[i - 1]) st2 = false;
	}
	if (st2){
		pair <int, int> p[n];
		for (int i = 0; i < n; i++){
			p[i].fi = s[i]; p[i].se = i;
		}
		sort(p, p + n);
		for (int i = 0; i < m; i++){
			cin >> x >> y;
			x -= 1; y -= 1;
			edg[x].pb(y); edg[y].pb(x);
		}
		vector <vector <int> > v;
		for (int i = 0; i < n; i++){
			vector <int> nx;
			nx.pb(p[i].se);
			while (i != n - 1){
				if (p[i + 1].fi == p[i].fi){
					nx.pb(p[i + 1].se);
				}
				else break;
				i += 1;
			}
			v.pb(nx);
		}
		init(n);
		for (auto tmp : v){
			for (auto nd : tmp){
				active[nd] = 1;
				for (auto nx : edg[nd]){
					if (active[nx]) merge(nx, nd);
				}
			}
			for (auto nd : tmp){
				powe[nd] = stronk(nd);
			}
		}
		for (auto nd : v.back()){
			ans[nd] = 1;
		}
		for (int i = n - 1; i >= 0; i--){
			int cur = p[i].se;
			if (!ans[cur]) continue;
			queue <int> q;
			q.push(cur);
			while (!q.empty()){
				int curnd = q.front();
				q.pop();
				for (auto nx : edg[curnd]){
					//if (cur == 1) cerr << powe[nx] << ' ' << 
					if (!ans[nx] and powe[nx] >= s[curnd]){
						ans[nx] = 1;
						q.push(nx);
					}
				}
			}
		}
		for (int i = 0; i < n; i++) cout << ans[i];
		return 0;
	}
	pair <int, int> p[n];
	for (int i = 0; i < n; i++){
		p[i].fi = s[i]; p[i].se = i;
	}
	sort(p, p + n);
	for (int i = 0; i < m; i++){
		cin >> x >> y;
		x -= 1; y -= 1;
		edg[x].pb(y); edg[y].pb(x);
	}
	vector <vector <int> > v;
	for (int i = 0; i < n; i++){
		vector <int> nx;
		nx.pb(p[i].se);
		while (i != n - 1){
			if (p[i + 1].fi == p[i].fi){
				nx.pb(p[i + 1].se);
			}
			else break;
			i += 1;
		}
		v.pb(nx);
	}
	init(n);
	for (auto tmp : v){
		for (auto nd : tmp){
			active[nd] = 1;
			for (auto nx : edg[nd]){
				if (active[nx]) merge(nx, nd);
			}
		}
		for (auto nd : tmp){
			powe[nd] = stronk(nd);
		}
	}
	for (auto nd : v.back()){
		ans[nd] = 1;
	}
	for (int i = n - 1; i >= 0; i--){
		int cur = p[i].se;
		if (requ[cur] <= powe[cur]) ans[cur] = 1;
		if (!ans[cur]) continue;
		queue <int> q;
		q.push(cur);
		vector <int> x;
		while (!q.empty()){
			int curnd = q.front();
			q.pop();
			for (auto nx : edg[curnd]){
				//if (cur == 1) cerr << powe[nx] << ' ' << 
				if (s[nx] <= s[cur] and requ[nx] > s[cur] ){
					requ[nx] = min(s[cur], requ[nx]);
					q.push(nx);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) cout << ans[i];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 20 ms 596 KB Output is correct
5 Correct 5 ms 692 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 17 ms 596 KB Output is correct
8 Correct 22 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 632 KB Output is correct
14 Correct 5 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 227 ms 34544 KB Output is correct
4 Correct 179 ms 30740 KB Output is correct
5 Correct 222 ms 37884 KB Output is correct
6 Correct 246 ms 36688 KB Output is correct
7 Correct 283 ms 39052 KB Output is correct
8 Correct 206 ms 31316 KB Output is correct
9 Correct 197 ms 37672 KB Output is correct
10 Correct 154 ms 36400 KB Output is correct
11 Correct 161 ms 33508 KB Output is correct
12 Correct 184 ms 29620 KB Output is correct
13 Correct 148 ms 31212 KB Output is correct
14 Correct 146 ms 30960 KB Output is correct
15 Correct 209 ms 38136 KB Output is correct
16 Correct 120 ms 37080 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 603 ms 33584 KB Output is correct
3 Correct 609 ms 31424 KB Output is correct
4 Correct 186 ms 28436 KB Output is correct
5 Correct 151 ms 27548 KB Output is correct
6 Correct 597 ms 33712 KB Output is correct
7 Execution timed out 1078 ms 33316 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 340 ms 25512 KB Output is correct
3 Correct 304 ms 25508 KB Output is correct
4 Correct 325 ms 25600 KB Output is correct
5 Correct 228 ms 26840 KB Output is correct
6 Correct 182 ms 25768 KB Output is correct
7 Correct 160 ms 28452 KB Output is correct
8 Correct 96 ms 28176 KB Output is correct
9 Correct 143 ms 15408 KB Output is correct
10 Correct 169 ms 26780 KB Output is correct
11 Correct 159 ms 25040 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 20 ms 596 KB Output is correct
5 Correct 5 ms 692 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 17 ms 596 KB Output is correct
8 Correct 22 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 632 KB Output is correct
14 Correct 5 ms 596 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 227 ms 34544 KB Output is correct
18 Correct 179 ms 30740 KB Output is correct
19 Correct 222 ms 37884 KB Output is correct
20 Correct 246 ms 36688 KB Output is correct
21 Correct 283 ms 39052 KB Output is correct
22 Correct 206 ms 31316 KB Output is correct
23 Correct 197 ms 37672 KB Output is correct
24 Correct 154 ms 36400 KB Output is correct
25 Correct 161 ms 33508 KB Output is correct
26 Correct 184 ms 29620 KB Output is correct
27 Correct 148 ms 31212 KB Output is correct
28 Correct 146 ms 30960 KB Output is correct
29 Correct 209 ms 38136 KB Output is correct
30 Correct 120 ms 37080 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 603 ms 33584 KB Output is correct
33 Correct 609 ms 31424 KB Output is correct
34 Correct 186 ms 28436 KB Output is correct
35 Correct 151 ms 27548 KB Output is correct
36 Correct 597 ms 33712 KB Output is correct
37 Execution timed out 1078 ms 33316 KB Time limit exceeded
38 Halted 0 ms 0 KB -