oj.uz

Submission #711094

# Submission time Handle Problem Language Result Execution time Memory
711094 2023-03-16T08:32:50 Z YeoBL Stranded Far From Home (BOI22_island) C++14
10 / 100
 218 ms 35872 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;
		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];
}

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 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 217 ms 35872 KB Output is correct
4 Correct 153 ms 27212 KB Output is correct
5 Correct 200 ms 33164 KB Output is correct
6 Correct 218 ms 31560 KB Output is correct
7 Correct 206 ms 33256 KB Output is correct
8 Correct 199 ms 25364 KB Output is correct
9 Correct 173 ms 31832 KB Output is correct
10 Correct 125 ms 31204 KB Output is correct
11 Correct 146 ms 28464 KB Output is correct
12 Correct 140 ms 25152 KB Output is correct
13 Correct 119 ms 26792 KB Output is correct
14 Correct 137 ms 26400 KB Output is correct
15 Correct 180 ms 32144 KB Output is correct
16 Correct 109 ms 31868 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 204 ms 31772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 216 ms 24072 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 0 ms 340 KB Output is correct
4 Incorrect 2 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -