oj.uz

답안 #725614

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725614 2023-04-17T18:35:49 Z WonderfulWhale Stranded Far From Home (BOI22_island) C++17
20 / 100
 1000 ms 206844 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: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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 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 15292 KB Output is correct
5 Correct 13 ms 15516 KB Output is correct
6 Correct 9 ms 14832 KB Output is correct
7 Correct 11 ms 15316 KB Output is correct
8 Correct 11 ms 15220 KB Output is correct
9 Correct 9 ms 15060 KB Output is correct
10 Correct 11 ms 15700 KB Output is correct
11 Correct 14 ms 15700 KB Output is correct
12 Correct 12 ms 15820 KB Output is correct
13 Correct 10 ms 14828 KB Output is correct
14 Correct 11 ms 15188 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14440 KB Output is correct
3 Correct 363 ms 106520 KB Output is correct
4 Correct 199 ms 50964 KB Output is correct
5 Correct 640 ms 147012 KB Output is correct
6 Correct 672 ms 148604 KB Output is correct
7 Correct 693 ms 153388 KB Output is correct
8 Correct 209 ms 50984 KB Output is correct
9 Correct 720 ms 206844 KB Output is correct
10 Correct 284 ms 93176 KB Output is correct
11 Correct 165 ms 51644 KB Output is correct
12 Correct 241 ms 52288 KB Output is correct
13 Correct 175 ms 50020 KB Output is correct
14 Correct 179 ms 50028 KB Output is correct
15 Correct 343 ms 96712 KB Output is correct
16 Correct 280 ms 96052 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 908 ms 175828 KB Output is correct
3 Correct 949 ms 174700 KB Output is correct
4 Correct 182 ms 54016 KB Output is correct
5 Execution timed out 1075 ms 52484 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 677 ms 102656 KB Output is correct
3 Correct 621 ms 113292 KB Output is correct
4 Correct 700 ms 124420 KB Output is correct
5 Correct 231 ms 55000 KB Output is correct
6 Execution timed out 1086 ms 54396 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 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 15292 KB Output is correct
5 Correct 13 ms 15516 KB Output is correct
6 Correct 9 ms 14832 KB Output is correct
7 Correct 11 ms 15316 KB Output is correct
8 Correct 11 ms 15220 KB Output is correct
9 Correct 9 ms 15060 KB Output is correct
10 Correct 11 ms 15700 KB Output is correct
11 Correct 14 ms 15700 KB Output is correct
12 Correct 12 ms 15820 KB Output is correct
13 Correct 10 ms 14828 KB Output is correct
14 Correct 11 ms 15188 KB Output is correct
15 Correct 8 ms 14420 KB Output is correct
16 Correct 7 ms 14440 KB Output is correct
17 Correct 363 ms 106520 KB Output is correct
18 Correct 199 ms 50964 KB Output is correct
19 Correct 640 ms 147012 KB Output is correct
20 Correct 672 ms 148604 KB Output is correct
21 Correct 693 ms 153388 KB Output is correct
22 Correct 209 ms 50984 KB Output is correct
23 Correct 720 ms 206844 KB Output is correct
24 Correct 284 ms 93176 KB Output is correct
25 Correct 165 ms 51644 KB Output is correct
26 Correct 241 ms 52288 KB Output is correct
27 Correct 175 ms 50020 KB Output is correct
28 Correct 179 ms 50028 KB Output is correct
29 Correct 343 ms 96712 KB Output is correct
30 Correct 280 ms 96052 KB Output is correct
31 Correct 9 ms 14420 KB Output is correct
32 Correct 908 ms 175828 KB Output is correct
33 Correct 949 ms 174700 KB Output is correct
34 Correct 182 ms 54016 KB Output is correct
35 Execution timed out 1075 ms 52484 KB Time limit exceeded
36 Halted 0 ms 0 KB -