oj.uz

Submission #711047

# Submission time Handle Problem Language Result Execution time Memory
711047 2023-03-16T07:39:54 Z YeoBL Stranded Far From Home (BOI22_island) C++14
10 / 100
 206 ms 34760 KB 
#include <bits/stdc++.h>
using namespace std;
#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];
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, mini; cin >> n >> m; 
	vector <int> edg[n];
	for (int i = 0; i < n; i++) cin >> s[i];
	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;
		mini = s[nd];
	}
	for (int i = n - 1; i >= 0; i--){
		int cur = p[i].se;
		if (ans[cur]) continue;
		for (auto x : edg[cur]){
			if (ans[x] and s[x] <= powe[cur]) ans[cur] = 1;
		}
		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 (!ans[nx] and s[nx] == s[cur]){
					ans[nx] = 1;
					q.push(nx);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) cout << ans[i];
}

Compilation message

island.cpp: In function 'int32_t main()':
island.cpp:33:18: warning: variable 'mini' set but not used [-Wunused-but-set-variable]
   33 |  int n, m, x, y, mini; cin >> n >> m;
      |                  ^~~~

Subtask #1
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 Incorrect 2 ms 596 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 168 ms 32976 KB Output is correct
4 Correct 162 ms 27336 KB Output is correct
5 Correct 182 ms 33632 KB Output is correct
6 Correct 187 ms 32352 KB Output is correct
7 Correct 196 ms 34760 KB Output is correct
8 Correct 196 ms 27024 KB Output is correct
9 Correct 191 ms 33008 KB Output is correct
10 Correct 124 ms 32924 KB Output is correct
11 Correct 128 ms 30104 KB Output is correct
12 Correct 190 ms 26292 KB Output is correct
13 Correct 132 ms 27844 KB Output is correct
14 Correct 139 ms 27704 KB Output is correct
15 Correct 206 ms 33776 KB Output is correct
16 Correct 123 ms 33628 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 Incorrect 206 ms 31752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 197 ms 24004 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 Incorrect 2 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -