oj.uz

Submission #725618

# Submission time Handle Problem Language Result Execution time Memory
725618 2023-04-17T18:39:59 Z WonderfulWhale Stranded Far From Home (BOI22_island) C++17
50 / 100
 1000 ms 154940 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

const int MAXN = 200009;

int tab[MAXN];
vector<int> G[MAXN];
bool ans[MAXN];
map<int, vector<int>> M;
vector<pair<int, pii>> edges;

int p[MAXN];
int sum[MAXN];
multiset<pii> S[MAXN];
vector<int> cost;
vector<tuple<int, int, int, int, vector<pii>>> undo_list;

void undo() {
	if(undo_list.empty()) return;
	auto &[y, old_p, x, old_sum, added_values] = undo_list.back();
	p[y] = old_p;
	sum[x] = old_sum;
	for(pii val:added_values) {
		S[x].erase(S[x].find(val));
	}
	undo_list.pop_back();
	cost.pop_back();
}

int Find(int x) {
	return p[x]==x?x:Find(p[x]);
}

void Union(int x, int y, int c) {
	int X = Find(x);
	int Y = Find(y);
	if(X==Y) return;
	if(sz(S[X])<sz(S[Y])) swap(X, Y);
	undo_list.push_back({Y, p[Y], X, sum[X], {}});
	cost.pb(c);
	p[Y] = X;
	sum[X] += sum[Y];
	sum[X] = min(sum[X], 1000000009);
	vector<pii> &added_values = get<4>(undo_list.back());
	for(pii val:S[Y]) {
		S[X].insert(val);
		added_values.pb(val);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;
	int Max = 0;
	for(int i=1;i<=n;i++) {
		cin >> tab[i];
		M[-tab[i]].pb(i);
		Max = max(Max, tab[i]);
	}
	for(int i=0;i<m;i++) {
		int a, b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
		edges.pb({max(tab[a], tab[b]), {a, b}});
	}
	for(int i=1;i<=n;i++) {
		p[i] = i;
		sum[i] = tab[i];
		for(int x:G[i]) {
			if(tab[x]>tab[i]) {
				S[i].insert({tab[x], x});
			}
		}
	}
	sort(all(edges));
	for(auto x:edges) {
		Union(x.nd.st, x.nd.nd, x.st);
	}
	for(int x:M[-Max]) {
		ans[x] = true;
	}
	M.erase(-Max);
	while(sz(cost)&&cost.back()==Max) undo();
	for(auto &x:M) {
		for(int y:x.nd) {
			int Y = Find(y);
			auto it = S[Y].upper_bound({sum[Y], 1e9});
			if(it!=S[Y].begin()) {
				it--;
				if(ans[it->nd]) {
					ans[y] = true;
				}
			}
		}
		while(sz(cost)&&cost.back()==-x.st) undo();
	}
	for(int i=1;i<=n;i++) {
		cout << ans[i];
	}
	cout << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14372 KB Output is correct
4 Correct 10 ms 15052 KB Output is correct
5 Correct 11 ms 15188 KB Output is correct
6 Correct 9 ms 14676 KB Output is correct
7 Correct 10 ms 15048 KB Output is correct
8 Correct 10 ms 15060 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct
10 Correct 12 ms 15316 KB Output is correct
11 Correct 11 ms 15344 KB Output is correct
12 Correct 12 ms 15444 KB Output is correct
13 Correct 9 ms 14676 KB Output is correct
14 Correct 14 ms 14928 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 324 ms 87328 KB Output is correct
4 Correct 158 ms 39236 KB Output is correct
5 Correct 621 ms 115264 KB Output is correct
6 Correct 605 ms 114888 KB Output is correct
7 Correct 626 ms 120080 KB Output is correct
8 Correct 208 ms 39300 KB Output is correct
9 Correct 612 ms 154940 KB Output is correct
10 Correct 265 ms 76764 KB Output is correct
11 Correct 153 ms 39740 KB Output is correct
12 Correct 195 ms 39896 KB Output is correct
13 Correct 154 ms 39000 KB Output is correct
14 Correct 157 ms 38944 KB Output is correct
15 Correct 324 ms 81272 KB Output is correct
16 Correct 252 ms 80600 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 843 ms 134620 KB Output is correct
3 Correct 812 ms 129548 KB Output is correct
4 Correct 175 ms 39136 KB Output is correct
5 Execution timed out 1074 ms 39236 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 544 ms 76120 KB Output is correct
3 Correct 677 ms 81120 KB Output is correct
4 Correct 855 ms 88772 KB Output is correct
5 Correct 276 ms 39092 KB Output is correct
6 Correct 968 ms 38664 KB Output is correct
7 Correct 155 ms 44092 KB Output is correct
8 Correct 226 ms 52680 KB Output is correct
9 Correct 332 ms 58944 KB Output is correct
10 Correct 370 ms 41920 KB Output is correct
11 Correct 321 ms 65180 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14372 KB Output is correct
4 Correct 10 ms 15052 KB Output is correct
5 Correct 11 ms 15188 KB Output is correct
6 Correct 9 ms 14676 KB Output is correct
7 Correct 10 ms 15048 KB Output is correct
8 Correct 10 ms 15060 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct
10 Correct 12 ms 15316 KB Output is correct
11 Correct 11 ms 15344 KB Output is correct
12 Correct 12 ms 15444 KB Output is correct
13 Correct 9 ms 14676 KB Output is correct
14 Correct 14 ms 14928 KB Output is correct
15 Correct 7 ms 14420 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Correct 324 ms 87328 KB Output is correct
18 Correct 158 ms 39236 KB Output is correct
19 Correct 621 ms 115264 KB Output is correct
20 Correct 605 ms 114888 KB Output is correct
21 Correct 626 ms 120080 KB Output is correct
22 Correct 208 ms 39300 KB Output is correct
23 Correct 612 ms 154940 KB Output is correct
24 Correct 265 ms 76764 KB Output is correct
25 Correct 153 ms 39740 KB Output is correct
26 Correct 195 ms 39896 KB Output is correct
27 Correct 154 ms 39000 KB Output is correct
28 Correct 157 ms 38944 KB Output is correct
29 Correct 324 ms 81272 KB Output is correct
30 Correct 252 ms 80600 KB Output is correct
31 Correct 7 ms 14420 KB Output is correct
32 Correct 843 ms 134620 KB Output is correct
33 Correct 812 ms 129548 KB Output is correct
34 Correct 175 ms 39136 KB Output is correct
35 Execution timed out 1074 ms 39236 KB Time limit exceeded
36 Halted 0 ms 0 KB -