oj.uz

답안 #883006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883006 2023-12-04T11:49:23 Z serifefedartar 다리 (APIO19_bridges) C++17
100 / 100
 1609 ms 12372 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 1e5 + 10000;

const int SQRT = 1000;
struct Edge {
	int from, to, w, id;
	Edge() { }
	Edge(int _from, int _to, int _w, int _id) : from(_from), to(_to), w(_w), id(_id) { }
};

struct Query {
	int type, node, w, id;
	Query() { }
	Query(int _type, int _node, int _w, int _id) : type(_type), node(_node), w(_w), id(_id) { }
}; 

vector<Edge> edges, srt;
Query queries[MAXN];
stack<pair<int,int>> st;
int par[MAXN], sz[MAXN], ans[MAXN], taken[MAXN], vis[MAXN], cnt2[MAXN];
int find(int node) {
	if (node == par[node])
		return node;
	return find(par[node]);
}

int cnt = 0;
void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return ;
	if (sz[b] > sz[a])
		swap(a, b);
	st.push({b, sz[b]});
	cnt++;
	sz[a] += sz[b];
	par[b] = a;
}

void rollback(int k) {
	while(st.size() && k--) {
		int nd = st.top().f;
		int siz = st.top().s;
		int pr = find(nd);
		st.pop();
		sz[nd] = siz;
		sz[pr] -= siz; 
		par[nd] = nd;
	}
}

void reset() {
	st = stack<pair<int,int>>();
	for (int i = 0; i < MAXN; i++)
		par[i] = i, sz[i] = 1;
}

int main() {
	int n, m, q;
	cin >> n >> m;

	edges = vector<Edge>(m);
	for (int i = 0; i < m; i++) {
		cin >> edges[i].from >> edges[i].to >> edges[i].w;
		edges[i].id = i;
	}

	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> queries[i].type >> queries[i].node >> queries[i].w;
		if (queries[i].type == 1)
			queries[i].node--;
		queries[i].id = i;
	}

	for (int firstQ = 0; firstQ < q; firstQ += SQRT) {
		srt = edges;
		sort(srt.begin(), srt.end(), [&](Edge A, Edge B) {
			return A.w > B.w;
		});

		int lastQ = min(firstQ + SQRT, q - 1);

		vector<Query> update, ask;
		for (int i = firstQ; i <= lastQ; i++) {
			if (queries[i].type == 1) {
				update.push_back(queries[i]);
				taken[queries[i].node]++;
			} else
				ask.push_back(queries[i]);
		}
		reverse(update.begin(), update.end());
		sort(ask.begin(), ask.end(), [&](Query A, Query B) {
			return A.w < B.w;
		});
		reset();

		for (auto u : srt) {
			if (taken[u.id])
				continue;
			vector<int> v;
			while (ask.size() && ask.back().w > u.w) {
				cnt = 0;
				v = vector<int>();
				for (auto u : update) {
					if (vis[u.node] || u.id > ask.back().id) {
						cnt2[u.node]++;
						v.push_back(u.node);
						if (cnt2[u.node] == taken[u.node] && edges[u.node].w >= ask.back().w)
							unite(edges[u.node].from, edges[u.node].to);
						continue;
					}
					vis[u.node] = true;
					if (u.w >= ask.back().w)
						unite(edges[u.node].from, edges[u.node].to);
				}
				ans[ask.back().id] = sz[find(ask.back().node)];
			
				rollback(cnt);
				for (auto u : update)
					vis[u.node] = false;
				for (auto u : v)
					cnt2[u] = 0;
				ask.pop_back();
			}
			unite(u.from, u.to);
		}

		while (ask.size()) {
			cnt = 0;
			vector<int> v;
			for (auto u : update) {
				if (vis[u.node] || u.id > ask.back().id) {
					v.push_back(u.node);
					cnt2[u.node]++;
					if (cnt2[u.node] == taken[u.node] && edges[u.node].w >= ask.back().w)
						unite(edges[u.node].from, edges[u.node].to);
					continue;
				}
				vis[u.node] = true;
				if (u.w >= ask.back().w)
					unite(edges[u.node].from, edges[u.node].to);
			}
			ans[ask.back().id] = sz[find(ask.back().node)];

			rollback(cnt);
			for (auto u : update)
				vis[u.node] = false;
			for (auto u : v)
				cnt2[u] = 0;
			ask.pop_back();
		}

		rollback(1e7);
		for (int i = update.size() - 1; i >= 0; i--) {
			taken[update[i].node]--;
			edges[update[i].node].w = update[i].w;
		}
	}

	for (int i = 0; i < q; i++) {
		if (queries[i].type == 2)
			cout << ans[i] << "\n";
	}
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 28 ms 4616 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 23 ms 4444 KB Output is correct
6 Correct 22 ms 4588 KB Output is correct
7 Correct 21 ms 4440 KB Output is correct
8 Correct 24 ms 4440 KB Output is correct
9 Correct 21 ms 4440 KB Output is correct
10 Correct 24 ms 4588 KB Output is correct
11 Correct 24 ms 4580 KB Output is correct
12 Correct 24 ms 4440 KB Output is correct
13 Correct 28 ms 4572 KB Output is correct
14 Correct 27 ms 4444 KB Output is correct
15 Correct 26 ms 4444 KB Output is correct
16 Correct 21 ms 4544 KB Output is correct
17 Correct 21 ms 4444 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 949 ms 6848 KB Output is correct
2 Correct 984 ms 9620 KB Output is correct
3 Correct 995 ms 9540 KB Output is correct
4 Correct 987 ms 9564 KB Output is correct
5 Correct 961 ms 9572 KB Output is correct
6 Correct 1189 ms 9536 KB Output is correct
7 Correct 1245 ms 9548 KB Output is correct
8 Correct 1179 ms 9812 KB Output is correct
9 Correct 68 ms 5908 KB Output is correct
10 Correct 733 ms 8344 KB Output is correct
11 Correct 713 ms 8352 KB Output is correct
12 Correct 790 ms 9436 KB Output is correct
13 Correct 875 ms 9684 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 783 ms 5972 KB Output is correct
2 Correct 523 ms 6464 KB Output is correct
3 Correct 820 ms 8276 KB Output is correct
4 Correct 735 ms 8424 KB Output is correct
5 Correct 78 ms 6052 KB Output is correct
6 Correct 768 ms 8784 KB Output is correct
7 Correct 705 ms 8308 KB Output is correct
8 Correct 651 ms 8480 KB Output is correct
9 Correct 514 ms 8508 KB Output is correct
10 Correct 476 ms 8360 KB Output is correct
11 Correct 540 ms 8532 KB Output is correct
12 Correct 496 ms 8300 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1163 ms 8348 KB Output is correct
2 Correct 66 ms 4692 KB Output is correct
3 Correct 150 ms 7508 KB Output is correct
4 Correct 100 ms 7508 KB Output is correct
5 Correct 632 ms 8492 KB Output is correct
6 Correct 1069 ms 8392 KB Output is correct
7 Correct 616 ms 8364 KB Output is correct
8 Correct 550 ms 6948 KB Output is correct
9 Correct 557 ms 7048 KB Output is correct
10 Correct 551 ms 6692 KB Output is correct
11 Correct 836 ms 7412 KB Output is correct
12 Correct 827 ms 7440 KB Output is correct
13 Correct 845 ms 7572 KB Output is correct
14 Correct 599 ms 8572 KB Output is correct
15 Correct 604 ms 8608 KB Output is correct
16 Correct 1108 ms 8452 KB Output is correct
17 Correct 1125 ms 8368 KB Output is correct
18 Correct 1118 ms 8440 KB Output is correct
19 Correct 1113 ms 8328 KB Output is correct
20 Correct 945 ms 8184 KB Output is correct
21 Correct 933 ms 8172 KB Output is correct
22 Correct 1088 ms 8448 KB Output is correct
23 Correct 648 ms 7944 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 949 ms 6848 KB Output is correct
2 Correct 984 ms 9620 KB Output is correct
3 Correct 995 ms 9540 KB Output is correct
4 Correct 987 ms 9564 KB Output is correct
5 Correct 961 ms 9572 KB Output is correct
6 Correct 1189 ms 9536 KB Output is correct
7 Correct 1245 ms 9548 KB Output is correct
8 Correct 1179 ms 9812 KB Output is correct
9 Correct 68 ms 5908 KB Output is correct
10 Correct 733 ms 8344 KB Output is correct
11 Correct 713 ms 8352 KB Output is correct
12 Correct 790 ms 9436 KB Output is correct
13 Correct 875 ms 9684 KB Output is correct
14 Correct 783 ms 5972 KB Output is correct
15 Correct 523 ms 6464 KB Output is correct
16 Correct 820 ms 8276 KB Output is correct
17 Correct 735 ms 8424 KB Output is correct
18 Correct 78 ms 6052 KB Output is correct
19 Correct 768 ms 8784 KB Output is correct
20 Correct 705 ms 8308 KB Output is correct
21 Correct 651 ms 8480 KB Output is correct
22 Correct 514 ms 8508 KB Output is correct
23 Correct 476 ms 8360 KB Output is correct
24 Correct 540 ms 8532 KB Output is correct
25 Correct 496 ms 8300 KB Output is correct
26 Correct 927 ms 9516 KB Output is correct
27 Correct 1125 ms 9576 KB Output is correct
28 Correct 992 ms 9548 KB Output is correct
29 Correct 793 ms 9656 KB Output is correct
30 Correct 1118 ms 9380 KB Output is correct
31 Correct 1047 ms 9572 KB Output is correct
32 Correct 1161 ms 9348 KB Output is correct
33 Correct 987 ms 9568 KB Output is correct
34 Correct 1041 ms 9676 KB Output is correct
35 Correct 1010 ms 9476 KB Output is correct
36 Correct 828 ms 9912 KB Output is correct
37 Correct 824 ms 9724 KB Output is correct
38 Correct 826 ms 9680 KB Output is correct
39 Correct 675 ms 9460 KB Output is correct
40 Correct 646 ms 9556 KB Output is correct
41 Correct 642 ms 9832 KB Output is correct
42 Correct 666 ms 9432 KB Output is correct
43 Correct 679 ms 9428 KB Output is correct
44 Correct 666 ms 9432 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 28 ms 4616 KB Output is correct
4 Correct 7 ms 4444 KB Output is correct
5 Correct 23 ms 4444 KB Output is correct
6 Correct 22 ms 4588 KB Output is correct
7 Correct 21 ms 4440 KB Output is correct
8 Correct 24 ms 4440 KB Output is correct
9 Correct 21 ms 4440 KB Output is correct
10 Correct 24 ms 4588 KB Output is correct
11 Correct 24 ms 4580 KB Output is correct
12 Correct 24 ms 4440 KB Output is correct
13 Correct 28 ms 4572 KB Output is correct
14 Correct 27 ms 4444 KB Output is correct
15 Correct 26 ms 4444 KB Output is correct
16 Correct 21 ms 4544 KB Output is correct
17 Correct 21 ms 4444 KB Output is correct
18 Correct 949 ms 6848 KB Output is correct
19 Correct 984 ms 9620 KB Output is correct
20 Correct 995 ms 9540 KB Output is correct
21 Correct 987 ms 9564 KB Output is correct
22 Correct 961 ms 9572 KB Output is correct
23 Correct 1189 ms 9536 KB Output is correct
24 Correct 1245 ms 9548 KB Output is correct
25 Correct 1179 ms 9812 KB Output is correct
26 Correct 68 ms 5908 KB Output is correct
27 Correct 733 ms 8344 KB Output is correct
28 Correct 713 ms 8352 KB Output is correct
29 Correct 790 ms 9436 KB Output is correct
30 Correct 875 ms 9684 KB Output is correct
31 Correct 783 ms 5972 KB Output is correct
32 Correct 523 ms 6464 KB Output is correct
33 Correct 820 ms 8276 KB Output is correct
34 Correct 735 ms 8424 KB Output is correct
35 Correct 78 ms 6052 KB Output is correct
36 Correct 768 ms 8784 KB Output is correct
37 Correct 705 ms 8308 KB Output is correct
38 Correct 651 ms 8480 KB Output is correct
39 Correct 514 ms 8508 KB Output is correct
40 Correct 476 ms 8360 KB Output is correct
41 Correct 540 ms 8532 KB Output is correct
42 Correct 496 ms 8300 KB Output is correct
43 Correct 1163 ms 8348 KB Output is correct
44 Correct 66 ms 4692 KB Output is correct
45 Correct 150 ms 7508 KB Output is correct
46 Correct 100 ms 7508 KB Output is correct
47 Correct 632 ms 8492 KB Output is correct
48 Correct 1069 ms 8392 KB Output is correct
49 Correct 616 ms 8364 KB Output is correct
50 Correct 550 ms 6948 KB Output is correct
51 Correct 557 ms 7048 KB Output is correct
52 Correct 551 ms 6692 KB Output is correct
53 Correct 836 ms 7412 KB Output is correct
54 Correct 827 ms 7440 KB Output is correct
55 Correct 845 ms 7572 KB Output is correct
56 Correct 599 ms 8572 KB Output is correct
57 Correct 604 ms 8608 KB Output is correct
58 Correct 1108 ms 8452 KB Output is correct
59 Correct 1125 ms 8368 KB Output is correct
60 Correct 1118 ms 8440 KB Output is correct
61 Correct 1113 ms 8328 KB Output is correct
62 Correct 945 ms 8184 KB Output is correct
63 Correct 933 ms 8172 KB Output is correct
64 Correct 1088 ms 8448 KB Output is correct
65 Correct 648 ms 7944 KB Output is correct
66 Correct 927 ms 9516 KB Output is correct
67 Correct 1125 ms 9576 KB Output is correct
68 Correct 992 ms 9548 KB Output is correct
69 Correct 793 ms 9656 KB Output is correct
70 Correct 1118 ms 9380 KB Output is correct
71 Correct 1047 ms 9572 KB Output is correct
72 Correct 1161 ms 9348 KB Output is correct
73 Correct 987 ms 9568 KB Output is correct
74 Correct 1041 ms 9676 KB Output is correct
75 Correct 1010 ms 9476 KB Output is correct
76 Correct 828 ms 9912 KB Output is correct
77 Correct 824 ms 9724 KB Output is correct
78 Correct 826 ms 9680 KB Output is correct
79 Correct 675 ms 9460 KB Output is correct
80 Correct 646 ms 9556 KB Output is correct
81 Correct 642 ms 9832 KB Output is correct
82 Correct 666 ms 9432 KB Output is correct
83 Correct 679 ms 9428 KB Output is correct
84 Correct 666 ms 9432 KB Output is correct
85 Correct 1459 ms 12372 KB Output is correct
86 Correct 183 ms 9732 KB Output is correct
87 Correct 154 ms 9812 KB Output is correct
88 Correct 929 ms 10688 KB Output is correct
89 Correct 1414 ms 12136 KB Output is correct
90 Correct 935 ms 10568 KB Output is correct
91 Correct 1022 ms 9552 KB Output is correct
92 Correct 1018 ms 9552 KB Output is correct
93 Correct 1356 ms 9296 KB Output is correct
94 Correct 1350 ms 10700 KB Output is correct
95 Correct 1252 ms 10852 KB Output is correct
96 Correct 1334 ms 10828 KB Output is correct
97 Correct 788 ms 10876 KB Output is correct
98 Correct 776 ms 10568 KB Output is correct
99 Correct 1491 ms 12012 KB Output is correct
100 Correct 1459 ms 11984 KB Output is correct
101 Correct 1471 ms 12136 KB Output is correct
102 Correct 1609 ms 12112 KB Output is correct
103 Correct 1454 ms 11448 KB Output is correct
104 Correct 1414 ms 11388 KB Output is correct
105 Correct 1188 ms 11248 KB Output is correct
106 Correct 954 ms 10676 KB Output is correct
107 Correct 1080 ms 11256 KB Output is correct
108 Correct 1418 ms 12164 KB Output is correct
109 Correct 996 ms 10148 KB Output is correct