oj.uz

Submission #725604

# Submission time Handle Problem Language Result Execution time Memory
725604 2023-04-17T18:00:46 Z WonderfulWhale Stranded Far From Home (BOI22_island) C++17
10 / 100
 933 ms 210896 KB 
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#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:p[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];
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14328 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Incorrect 13 ms 15276 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 8 ms 14420 KB Output is correct
2 Correct 9 ms 14448 KB Output is correct
3 Correct 359 ms 110728 KB Output is correct
4 Correct 178 ms 53632 KB Output is correct
5 Correct 740 ms 150860 KB Output is correct
6 Correct 730 ms 152624 KB Output is correct
7 Correct 742 ms 157408 KB Output is correct
8 Correct 252 ms 54996 KB Output is correct
9 Correct 740 ms 210896 KB Output is correct
10 Correct 328 ms 96220 KB Output is correct
11 Correct 162 ms 54476 KB Output is correct
12 Correct 250 ms 54832 KB Output is correct
13 Correct 195 ms 52476 KB Output is correct
14 Correct 161 ms 52628 KB Output is correct
15 Correct 369 ms 100616 KB Output is correct
16 Correct 260 ms 99108 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Incorrect 933 ms 179604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14340 KB Output is correct
2 Incorrect 728 ms 106612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14328 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Incorrect 13 ms 15276 KB Output isn't correct
5 Halted 0 ms 0 KB -