oj.uz

답안 #725619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725619 2023-04-17T18:45:51 Z WonderfulWhale Stranded Far From Home (BOI22_island) C++17
20 / 100
 1000 ms 189768 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];
set<pair<int, pii>> S[MAXN];
vector<int> cost;
vector<tuple<int, int, int, int, vector<pair<int, 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(pair<int, pii> val:added_values) {
		S[x].erase(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<pair<int, pii>> &added_values = get<4>(undo_list.back());
	for(pair<int, 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, i}});
			}
		}
	}
	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, 1e9}});
			if(it!=S[Y].begin()) {
				it--;
				if(ans[it->nd.st]) {
					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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 10 ms 15188 KB Output is correct
5 Correct 11 ms 15288 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 10 ms 15060 KB Output is correct
8 Correct 10 ms 15088 KB Output is correct
9 Correct 8 ms 14744 KB Output is correct
10 Correct 11 ms 15548 KB Output is correct
11 Correct 12 ms 15452 KB Output is correct
12 Correct 14 ms 15700 KB Output is correct
13 Correct 8 ms 14692 KB Output is correct
14 Correct 9 ms 15060 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 332 ms 95880 KB Output is correct
4 Correct 168 ms 38984 KB Output is correct
5 Correct 632 ms 134136 KB Output is correct
6 Correct 747 ms 134888 KB Output is correct
7 Correct 750 ms 139960 KB Output is correct
8 Correct 178 ms 39068 KB Output is correct
9 Correct 699 ms 189768 KB Output is correct
10 Correct 271 ms 82964 KB Output is correct
11 Correct 157 ms 39752 KB Output is correct
12 Correct 171 ms 40192 KB Output is correct
13 Correct 170 ms 38992 KB Output is correct
14 Correct 158 ms 39088 KB Output is correct
15 Correct 330 ms 87604 KB Output is correct
16 Correct 247 ms 87024 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 905 ms 161268 KB Output is correct
3 Correct 799 ms 155920 KB Output is correct
4 Correct 156 ms 38916 KB Output is correct
5 Execution timed out 1095 ms 38944 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 560 ms 89304 KB Output is correct
3 Correct 601 ms 95996 KB Output is correct
4 Correct 661 ms 106376 KB Output is correct
5 Correct 181 ms 38968 KB Output is correct
6 Execution timed out 1087 ms 38528 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 10 ms 15188 KB Output is correct
5 Correct 11 ms 15288 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 10 ms 15060 KB Output is correct
8 Correct 10 ms 15088 KB Output is correct
9 Correct 8 ms 14744 KB Output is correct
10 Correct 11 ms 15548 KB Output is correct
11 Correct 12 ms 15452 KB Output is correct
12 Correct 14 ms 15700 KB Output is correct
13 Correct 8 ms 14692 KB Output is correct
14 Correct 9 ms 15060 KB Output is correct
15 Correct 7 ms 14420 KB Output is correct
16 Correct 7 ms 14432 KB Output is correct
17 Correct 332 ms 95880 KB Output is correct
18 Correct 168 ms 38984 KB Output is correct
19 Correct 632 ms 134136 KB Output is correct
20 Correct 747 ms 134888 KB Output is correct
21 Correct 750 ms 139960 KB Output is correct
22 Correct 178 ms 39068 KB Output is correct
23 Correct 699 ms 189768 KB Output is correct
24 Correct 271 ms 82964 KB Output is correct
25 Correct 157 ms 39752 KB Output is correct
26 Correct 171 ms 40192 KB Output is correct
27 Correct 170 ms 38992 KB Output is correct
28 Correct 158 ms 39088 KB Output is correct
29 Correct 330 ms 87604 KB Output is correct
30 Correct 247 ms 87024 KB Output is correct
31 Correct 7 ms 14420 KB Output is correct
32 Correct 905 ms 161268 KB Output is correct
33 Correct 799 ms 155920 KB Output is correct
34 Correct 156 ms 38916 KB Output is correct
35 Execution timed out 1095 ms 38944 KB Time limit exceeded
36 Halted 0 ms 0 KB -