oj.uz

Submission #711090

# Submission time Handle Problem Language Result Execution time Memory
711090 2023-03-16T08:31:17 Z YeoBL Stranded Far From Home (BOI22_island) C++14
10 / 100
 267 ms 37456 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 (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 1 ms 324 KB Output is correct
4 Incorrect 3 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 328 KB Output is correct
3 Correct 227 ms 33492 KB Output is correct
4 Correct 183 ms 28812 KB Output is correct
5 Correct 240 ms 35924 KB Output is correct
6 Correct 267 ms 34752 KB Output is correct
7 Correct 239 ms 37456 KB Output is correct
8 Correct 257 ms 29744 KB Output is correct
9 Correct 220 ms 35956 KB Output is correct
10 Correct 155 ms 34820 KB Output is correct
11 Correct 193 ms 31904 KB Output is correct
12 Correct 220 ms 27984 KB Output is correct
13 Correct 187 ms 29672 KB Output is correct
14 Correct 194 ms 29444 KB Output is correct
15 Correct 202 ms 36688 KB Output is correct
16 Correct 140 ms 35520 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Incorrect 259 ms 34760 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 241 ms 26988 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 324 KB Output is correct
4 Incorrect 3 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -