oj.uz

Submission #711048

# Submission time Handle Problem Language Result Execution time Memory
711048 2023-03-16T07:40:56 Z YeoBL Stranded Far From Home (BOI22_island) C++14
10 / 100
 221 ms 33044 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;
		if (powe[cur] < mini) 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);
				}
			}
		}
		mini = min(s[cur], mini);
	}
	for (int i = 0; i < n; i++) cout << ans[i];
}

Compilation message

island.cpp: In function 'int32_t main()':
island.cpp:33:18: warning: 'mini' may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |  int n, m, x, y, mini; cin >> n >> m;
      |                  ^~~~

Subtask #1
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 0 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 1 ms 340 KB Output is correct
3 Correct 180 ms 33020 KB Output is correct
4 Correct 128 ms 26080 KB Output is correct
5 Correct 184 ms 31976 KB Output is correct
6 Correct 190 ms 30816 KB Output is correct
7 Correct 221 ms 33044 KB Output is correct
8 Correct 205 ms 25444 KB Output is correct
9 Correct 198 ms 31544 KB Output is correct
10 Correct 128 ms 31236 KB Output is correct
11 Correct 121 ms 28536 KB Output is correct
12 Correct 147 ms 25100 KB Output is correct
13 Correct 133 ms 26792 KB Output is correct
14 Correct 145 ms 26416 KB Output is correct
15 Correct 183 ms 32136 KB Output is correct
16 Correct 109 ms 31860 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 214 ms 31764 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 188 ms 24016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 0 ms 340 KB Output is correct
4 Incorrect 2 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -