oj.uz

Submission #463898

# Submission time Handle Problem Language Result Execution time Memory
463898 2021-08-12T01:52:40 Z czhang2718 Bridges (APIO19_bridges) C++14
100 / 100
 2496 ms 29208 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const int B = 1000;

int n, m, q;

stack<int> stck;
int sz[100001], cmp[100001];

void reset() {
	iota(cmp + 1, cmp + 1 + n, 1);
	fill(sz + 1, sz + n + 1, 1);
}

inline int find(int a) {
	while (cmp[a] != a) a = cmp[a];
	return a;
}

void onion(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (sz[a] > sz[b]) swap(a, b);
	stck.push(a);
	sz[b] += sz[a];
	cmp[a] = cmp[b];
}

void rollback(int x) {
	while (stck.size() > x) {
		int k = stck.top();
		stck.pop();
		sz[cmp[k]] -= sz[k];
		cmp[k] = k;
	}
}

int u[100001], v[100001], w[100001];
int t[100001], x[100001], y[100001];
bool changed[100001];
vector<int> to_join[B];
int ans[100001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	FOR(i, 1, m + 1) cin >> u[i] >> v[i] >> w[i];
	cin >> q;
	FOR(i, 1, q + 1) cin >> t[i] >> x[i] >> y[i];

	for (int l = 1; l <= q; l += B) {
		int r = min(q + 1, l + B);
		reset();
		fill(changed + 1, changed + m + 1, false);

		vector<int> ask, upd, unchanged;
		FOR(i, l, r) {
			if (t[i] == 1) {
				changed[x[i]] = true;
				upd.push_back(i);
			} else ask.push_back(i);
		}
		FOR(i, 1, m + 1) if (!changed[i]) unchanged.push_back(i);

		FOR(i, l, r) {
			if (t[i] == 1) w[x[i]] = y[i];
			else {
				to_join[i - l].clear();
				for (int j : upd) if (w[x[j]] >= y[i]) to_join[i - l].push_back(x[j]);
			}
		}

		sort(ask.begin(), ask.end(), [&](int a, int b) { return y[a] > y[b]; });
		sort(unchanged.begin(), unchanged.end(), [&](int a, int b) { return w[a] > w[b]; });

		int ptr = 0;
		for (int i : ask) {
			while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) {
				onion(u[unchanged[ptr]], v[unchanged[ptr]]);
				ptr++;
			}
			int prev_size = stck.size();
			for (int j : to_join[i - l]) onion(u[j], v[j]);
			ans[i] = sz[find(x[i])];
			rollback(prev_size);
		}
	}

	FOR(i, 1, q + 1) if (t[i] == 2) cout << ans[i] << '\n';
	return 0;
}

Compilation message

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:33:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |  while (stck.size() > x) {
      |         ~~~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) {
      |           ~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 39 ms 2676 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 40 ms 2884 KB Output is correct
6 Correct 30 ms 2580 KB Output is correct
7 Correct 36 ms 3424 KB Output is correct
8 Correct 40 ms 2628 KB Output is correct
9 Correct 48 ms 4292 KB Output is correct
10 Correct 42 ms 2768 KB Output is correct
11 Correct 49 ms 2604 KB Output is correct
12 Correct 51 ms 2848 KB Output is correct
13 Correct 48 ms 2760 KB Output is correct
14 Correct 46 ms 2600 KB Output is correct
15 Correct 49 ms 2628 KB Output is correct
16 Correct 45 ms 3948 KB Output is correct
17 Correct 48 ms 3356 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1474 ms 26072 KB Output is correct
2 Correct 1472 ms 26024 KB Output is correct
3 Correct 1470 ms 26144 KB Output is correct
4 Correct 1537 ms 25996 KB Output is correct
5 Correct 1543 ms 26476 KB Output is correct
6 Correct 2208 ms 27880 KB Output is correct
7 Correct 2210 ms 27864 KB Output is correct
8 Correct 2206 ms 27992 KB Output is correct
9 Correct 43 ms 2116 KB Output is correct
10 Correct 1254 ms 27948 KB Output is correct
11 Correct 1141 ms 27880 KB Output is correct
12 Correct 1276 ms 24664 KB Output is correct
13 Correct 1297 ms 27480 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1212 ms 18648 KB Output is correct
2 Correct 957 ms 9676 KB Output is correct
3 Correct 1463 ms 20576 KB Output is correct
4 Correct 1177 ms 18772 KB Output is correct
5 Correct 42 ms 1988 KB Output is correct
6 Correct 1356 ms 18824 KB Output is correct
7 Correct 1078 ms 18372 KB Output is correct
8 Correct 950 ms 18320 KB Output is correct
9 Correct 777 ms 17088 KB Output is correct
10 Correct 691 ms 16980 KB Output is correct
11 Correct 830 ms 19920 KB Output is correct
12 Correct 712 ms 19784 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1696 ms 24948 KB Output is correct
2 Correct 43 ms 1988 KB Output is correct
3 Correct 175 ms 2692 KB Output is correct
4 Correct 89 ms 2708 KB Output is correct
5 Correct 858 ms 24908 KB Output is correct
6 Correct 1659 ms 24928 KB Output is correct
7 Correct 850 ms 24852 KB Output is correct
8 Correct 806 ms 23964 KB Output is correct
9 Correct 803 ms 23968 KB Output is correct
10 Correct 801 ms 24048 KB Output is correct
11 Correct 1247 ms 24672 KB Output is correct
12 Correct 1224 ms 24752 KB Output is correct
13 Correct 1266 ms 25036 KB Output is correct
14 Correct 774 ms 25184 KB Output is correct
15 Correct 828 ms 25040 KB Output is correct
16 Correct 1669 ms 25280 KB Output is correct
17 Correct 1695 ms 25028 KB Output is correct
18 Correct 1670 ms 25336 KB Output is correct
19 Correct 1664 ms 25480 KB Output is correct
20 Correct 1393 ms 25340 KB Output is correct
21 Correct 1406 ms 25192 KB Output is correct
22 Correct 1609 ms 24824 KB Output is correct
23 Correct 954 ms 22912 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1474 ms 26072 KB Output is correct
2 Correct 1472 ms 26024 KB Output is correct
3 Correct 1470 ms 26144 KB Output is correct
4 Correct 1537 ms 25996 KB Output is correct
5 Correct 1543 ms 26476 KB Output is correct
6 Correct 2208 ms 27880 KB Output is correct
7 Correct 2210 ms 27864 KB Output is correct
8 Correct 2206 ms 27992 KB Output is correct
9 Correct 43 ms 2116 KB Output is correct
10 Correct 1254 ms 27948 KB Output is correct
11 Correct 1141 ms 27880 KB Output is correct
12 Correct 1276 ms 24664 KB Output is correct
13 Correct 1297 ms 27480 KB Output is correct
14 Correct 1212 ms 18648 KB Output is correct
15 Correct 957 ms 9676 KB Output is correct
16 Correct 1463 ms 20576 KB Output is correct
17 Correct 1177 ms 18772 KB Output is correct
18 Correct 42 ms 1988 KB Output is correct
19 Correct 1356 ms 18824 KB Output is correct
20 Correct 1078 ms 18372 KB Output is correct
21 Correct 950 ms 18320 KB Output is correct
22 Correct 777 ms 17088 KB Output is correct
23 Correct 691 ms 16980 KB Output is correct
24 Correct 830 ms 19920 KB Output is correct
25 Correct 712 ms 19784 KB Output is correct
26 Correct 1560 ms 26196 KB Output is correct
27 Correct 1874 ms 27984 KB Output is correct
28 Correct 1533 ms 26160 KB Output is correct
29 Correct 1093 ms 25748 KB Output is correct
30 Correct 1777 ms 27844 KB Output is correct
31 Correct 1865 ms 27944 KB Output is correct
32 Correct 1818 ms 28076 KB Output is correct
33 Correct 1549 ms 26076 KB Output is correct
34 Correct 1537 ms 26108 KB Output is correct
35 Correct 1553 ms 26096 KB Output is correct
36 Correct 1187 ms 25880 KB Output is correct
37 Correct 1150 ms 25884 KB Output is correct
38 Correct 1158 ms 25876 KB Output is correct
39 Correct 954 ms 24344 KB Output is correct
40 Correct 919 ms 24536 KB Output is correct
41 Correct 946 ms 24440 KB Output is correct
42 Correct 903 ms 26548 KB Output is correct
43 Correct 908 ms 26392 KB Output is correct
44 Correct 911 ms 26328 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 39 ms 2676 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 40 ms 2884 KB Output is correct
6 Correct 30 ms 2580 KB Output is correct
7 Correct 36 ms 3424 KB Output is correct
8 Correct 40 ms 2628 KB Output is correct
9 Correct 48 ms 4292 KB Output is correct
10 Correct 42 ms 2768 KB Output is correct
11 Correct 49 ms 2604 KB Output is correct
12 Correct 51 ms 2848 KB Output is correct
13 Correct 48 ms 2760 KB Output is correct
14 Correct 46 ms 2600 KB Output is correct
15 Correct 49 ms 2628 KB Output is correct
16 Correct 45 ms 3948 KB Output is correct
17 Correct 48 ms 3356 KB Output is correct
18 Correct 1474 ms 26072 KB Output is correct
19 Correct 1472 ms 26024 KB Output is correct
20 Correct 1470 ms 26144 KB Output is correct
21 Correct 1537 ms 25996 KB Output is correct
22 Correct 1543 ms 26476 KB Output is correct
23 Correct 2208 ms 27880 KB Output is correct
24 Correct 2210 ms 27864 KB Output is correct
25 Correct 2206 ms 27992 KB Output is correct
26 Correct 43 ms 2116 KB Output is correct
27 Correct 1254 ms 27948 KB Output is correct
28 Correct 1141 ms 27880 KB Output is correct
29 Correct 1276 ms 24664 KB Output is correct
30 Correct 1297 ms 27480 KB Output is correct
31 Correct 1212 ms 18648 KB Output is correct
32 Correct 957 ms 9676 KB Output is correct
33 Correct 1463 ms 20576 KB Output is correct
34 Correct 1177 ms 18772 KB Output is correct
35 Correct 42 ms 1988 KB Output is correct
36 Correct 1356 ms 18824 KB Output is correct
37 Correct 1078 ms 18372 KB Output is correct
38 Correct 950 ms 18320 KB Output is correct
39 Correct 777 ms 17088 KB Output is correct
40 Correct 691 ms 16980 KB Output is correct
41 Correct 830 ms 19920 KB Output is correct
42 Correct 712 ms 19784 KB Output is correct
43 Correct 1696 ms 24948 KB Output is correct
44 Correct 43 ms 1988 KB Output is correct
45 Correct 175 ms 2692 KB Output is correct
46 Correct 89 ms 2708 KB Output is correct
47 Correct 858 ms 24908 KB Output is correct
48 Correct 1659 ms 24928 KB Output is correct
49 Correct 850 ms 24852 KB Output is correct
50 Correct 806 ms 23964 KB Output is correct
51 Correct 803 ms 23968 KB Output is correct
52 Correct 801 ms 24048 KB Output is correct
53 Correct 1247 ms 24672 KB Output is correct
54 Correct 1224 ms 24752 KB Output is correct
55 Correct 1266 ms 25036 KB Output is correct
56 Correct 774 ms 25184 KB Output is correct
57 Correct 828 ms 25040 KB Output is correct
58 Correct 1669 ms 25280 KB Output is correct
59 Correct 1695 ms 25028 KB Output is correct
60 Correct 1670 ms 25336 KB Output is correct
61 Correct 1664 ms 25480 KB Output is correct
62 Correct 1393 ms 25340 KB Output is correct
63 Correct 1406 ms 25192 KB Output is correct
64 Correct 1609 ms 24824 KB Output is correct
65 Correct 954 ms 22912 KB Output is correct
66 Correct 1560 ms 26196 KB Output is correct
67 Correct 1874 ms 27984 KB Output is correct
68 Correct 1533 ms 26160 KB Output is correct
69 Correct 1093 ms 25748 KB Output is correct
70 Correct 1777 ms 27844 KB Output is correct
71 Correct 1865 ms 27944 KB Output is correct
72 Correct 1818 ms 28076 KB Output is correct
73 Correct 1549 ms 26076 KB Output is correct
74 Correct 1537 ms 26108 KB Output is correct
75 Correct 1553 ms 26096 KB Output is correct
76 Correct 1187 ms 25880 KB Output is correct
77 Correct 1150 ms 25884 KB Output is correct
78 Correct 1158 ms 25876 KB Output is correct
79 Correct 954 ms 24344 KB Output is correct
80 Correct 919 ms 24536 KB Output is correct
81 Correct 946 ms 24440 KB Output is correct
82 Correct 903 ms 26548 KB Output is correct
83 Correct 908 ms 26392 KB Output is correct
84 Correct 911 ms 26328 KB Output is correct
85 Correct 2250 ms 27584 KB Output is correct
86 Correct 219 ms 4856 KB Output is correct
87 Correct 142 ms 6160 KB Output is correct
88 Correct 1399 ms 29012 KB Output is correct
89 Correct 2222 ms 27384 KB Output is correct
90 Correct 1455 ms 29136 KB Output is correct
91 Correct 1594 ms 26268 KB Output is correct
92 Correct 1589 ms 26136 KB Output is correct
93 Correct 2280 ms 27840 KB Output is correct
94 Correct 1905 ms 27456 KB Output is correct
95 Correct 1870 ms 27524 KB Output is correct
96 Correct 2265 ms 29200 KB Output is correct
97 Correct 1048 ms 25696 KB Output is correct
98 Correct 1084 ms 28812 KB Output is correct
99 Correct 2223 ms 27752 KB Output is correct
100 Correct 2237 ms 27492 KB Output is correct
101 Correct 2281 ms 27720 KB Output is correct
102 Correct 2278 ms 27680 KB Output is correct
103 Correct 2496 ms 29180 KB Output is correct
104 Correct 2484 ms 29208 KB Output is correct
105 Correct 1799 ms 28940 KB Output is correct
106 Correct 1443 ms 28568 KB Output is correct
107 Correct 1692 ms 25784 KB Output is correct
108 Correct 2338 ms 27692 KB Output is correct
109 Correct 1700 ms 26896 KB Output is correct