oj.uz

Submission #576916

# Submission time Handle Problem Language Result Execution time Memory
576916 2022-06-13T19:12:30 Z training4usaco Bridges (APIO19_bridges) C++11
100 / 100
 1963 ms 32252 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 34 ms 2796 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 35 ms 3036 KB Output is correct
6 Correct 28 ms 2684 KB Output is correct
7 Correct 32 ms 3532 KB Output is correct
8 Correct 34 ms 2708 KB Output is correct
9 Correct 42 ms 4284 KB Output is correct
10 Correct 34 ms 2884 KB Output is correct
11 Correct 38 ms 2796 KB Output is correct
12 Correct 43 ms 2916 KB Output is correct
13 Correct 40 ms 2860 KB Output is correct
14 Correct 38 ms 2704 KB Output is correct
15 Correct 42 ms 2840 KB Output is correct
16 Correct 38 ms 4036 KB Output is correct
17 Correct 37 ms 3520 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1158 ms 26156 KB Output is correct
2 Correct 1187 ms 28932 KB Output is correct
3 Correct 1191 ms 28892 KB Output is correct
4 Correct 1248 ms 28880 KB Output is correct
5 Correct 1246 ms 29188 KB Output is correct
6 Correct 1818 ms 30560 KB Output is correct
7 Correct 1787 ms 30512 KB Output is correct
8 Correct 1797 ms 30472 KB Output is correct
9 Correct 34 ms 3404 KB Output is correct
10 Correct 995 ms 29640 KB Output is correct
11 Correct 918 ms 29608 KB Output is correct
12 Correct 1024 ms 27572 KB Output is correct
13 Correct 1042 ms 30124 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 18612 KB Output is correct
2 Correct 749 ms 11192 KB Output is correct
3 Correct 1154 ms 22748 KB Output is correct
4 Correct 945 ms 21296 KB Output is correct
5 Correct 32 ms 3384 KB Output is correct
6 Correct 1092 ms 21224 KB Output is correct
7 Correct 877 ms 20736 KB Output is correct
8 Correct 764 ms 20560 KB Output is correct
9 Correct 618 ms 19488 KB Output is correct
10 Correct 555 ms 19228 KB Output is correct
11 Correct 664 ms 22148 KB Output is correct
12 Correct 579 ms 22076 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1370 ms 24764 KB Output is correct
2 Correct 35 ms 3428 KB Output is correct
3 Correct 143 ms 4548 KB Output is correct
4 Correct 69 ms 4676 KB Output is correct
5 Correct 684 ms 27336 KB Output is correct
6 Correct 1334 ms 28672 KB Output is correct
7 Correct 691 ms 27348 KB Output is correct
8 Correct 654 ms 26528 KB Output is correct
9 Correct 649 ms 26652 KB Output is correct
10 Correct 661 ms 26724 KB Output is correct
11 Correct 1002 ms 27908 KB Output is correct
12 Correct 1000 ms 28076 KB Output is correct
13 Correct 1022 ms 27976 KB Output is correct
14 Correct 617 ms 27196 KB Output is correct
15 Correct 646 ms 27228 KB Output is correct
16 Correct 1350 ms 28908 KB Output is correct
17 Correct 1359 ms 28836 KB Output is correct
18 Correct 1351 ms 29212 KB Output is correct
19 Correct 1356 ms 29060 KB Output is correct
20 Correct 1116 ms 28396 KB Output is correct
21 Correct 1148 ms 28360 KB Output is correct
22 Correct 1309 ms 28452 KB Output is correct
23 Correct 757 ms 24976 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1158 ms 26156 KB Output is correct
2 Correct 1187 ms 28932 KB Output is correct
3 Correct 1191 ms 28892 KB Output is correct
4 Correct 1248 ms 28880 KB Output is correct
5 Correct 1246 ms 29188 KB Output is correct
6 Correct 1818 ms 30560 KB Output is correct
7 Correct 1787 ms 30512 KB Output is correct
8 Correct 1797 ms 30472 KB Output is correct
9 Correct 34 ms 3404 KB Output is correct
10 Correct 995 ms 29640 KB Output is correct
11 Correct 918 ms 29608 KB Output is correct
12 Correct 1024 ms 27572 KB Output is correct
13 Correct 1042 ms 30124 KB Output is correct
14 Correct 967 ms 18612 KB Output is correct
15 Correct 749 ms 11192 KB Output is correct
16 Correct 1154 ms 22748 KB Output is correct
17 Correct 945 ms 21296 KB Output is correct
18 Correct 32 ms 3384 KB Output is correct
19 Correct 1092 ms 21224 KB Output is correct
20 Correct 877 ms 20736 KB Output is correct
21 Correct 764 ms 20560 KB Output is correct
22 Correct 618 ms 19488 KB Output is correct
23 Correct 555 ms 19228 KB Output is correct
24 Correct 664 ms 22148 KB Output is correct
25 Correct 579 ms 22076 KB Output is correct
26 Correct 1222 ms 29100 KB Output is correct
27 Correct 1515 ms 30508 KB Output is correct
28 Correct 1255 ms 29092 KB Output is correct
29 Correct 889 ms 28404 KB Output is correct
30 Correct 1432 ms 30520 KB Output is correct
31 Correct 1468 ms 30480 KB Output is correct
32 Correct 1476 ms 30464 KB Output is correct
33 Correct 1225 ms 28796 KB Output is correct
34 Correct 1235 ms 28768 KB Output is correct
35 Correct 1246 ms 29116 KB Output is correct
36 Correct 927 ms 28576 KB Output is correct
37 Correct 920 ms 28592 KB Output is correct
38 Correct 914 ms 28452 KB Output is correct
39 Correct 764 ms 27252 KB Output is correct
40 Correct 746 ms 27264 KB Output is correct
41 Correct 742 ms 27048 KB Output is correct
42 Correct 742 ms 29044 KB Output is correct
43 Correct 741 ms 29052 KB Output is correct
44 Correct 747 ms 28848 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 34 ms 2796 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 35 ms 3036 KB Output is correct
6 Correct 28 ms 2684 KB Output is correct
7 Correct 32 ms 3532 KB Output is correct
8 Correct 34 ms 2708 KB Output is correct
9 Correct 42 ms 4284 KB Output is correct
10 Correct 34 ms 2884 KB Output is correct
11 Correct 38 ms 2796 KB Output is correct
12 Correct 43 ms 2916 KB Output is correct
13 Correct 40 ms 2860 KB Output is correct
14 Correct 38 ms 2704 KB Output is correct
15 Correct 42 ms 2840 KB Output is correct
16 Correct 38 ms 4036 KB Output is correct
17 Correct 37 ms 3520 KB Output is correct
18 Correct 1158 ms 26156 KB Output is correct
19 Correct 1187 ms 28932 KB Output is correct
20 Correct 1191 ms 28892 KB Output is correct
21 Correct 1248 ms 28880 KB Output is correct
22 Correct 1246 ms 29188 KB Output is correct
23 Correct 1818 ms 30560 KB Output is correct
24 Correct 1787 ms 30512 KB Output is correct
25 Correct 1797 ms 30472 KB Output is correct
26 Correct 34 ms 3404 KB Output is correct
27 Correct 995 ms 29640 KB Output is correct
28 Correct 918 ms 29608 KB Output is correct
29 Correct 1024 ms 27572 KB Output is correct
30 Correct 1042 ms 30124 KB Output is correct
31 Correct 967 ms 18612 KB Output is correct
32 Correct 749 ms 11192 KB Output is correct
33 Correct 1154 ms 22748 KB Output is correct
34 Correct 945 ms 21296 KB Output is correct
35 Correct 32 ms 3384 KB Output is correct
36 Correct 1092 ms 21224 KB Output is correct
37 Correct 877 ms 20736 KB Output is correct
38 Correct 764 ms 20560 KB Output is correct
39 Correct 618 ms 19488 KB Output is correct
40 Correct 555 ms 19228 KB Output is correct
41 Correct 664 ms 22148 KB Output is correct
42 Correct 579 ms 22076 KB Output is correct
43 Correct 1370 ms 24764 KB Output is correct
44 Correct 35 ms 3428 KB Output is correct
45 Correct 143 ms 4548 KB Output is correct
46 Correct 69 ms 4676 KB Output is correct
47 Correct 684 ms 27336 KB Output is correct
48 Correct 1334 ms 28672 KB Output is correct
49 Correct 691 ms 27348 KB Output is correct
50 Correct 654 ms 26528 KB Output is correct
51 Correct 649 ms 26652 KB Output is correct
52 Correct 661 ms 26724 KB Output is correct
53 Correct 1002 ms 27908 KB Output is correct
54 Correct 1000 ms 28076 KB Output is correct
55 Correct 1022 ms 27976 KB Output is correct
56 Correct 617 ms 27196 KB Output is correct
57 Correct 646 ms 27228 KB Output is correct
58 Correct 1350 ms 28908 KB Output is correct
59 Correct 1359 ms 28836 KB Output is correct
60 Correct 1351 ms 29212 KB Output is correct
61 Correct 1356 ms 29060 KB Output is correct
62 Correct 1116 ms 28396 KB Output is correct
63 Correct 1148 ms 28360 KB Output is correct
64 Correct 1309 ms 28452 KB Output is correct
65 Correct 757 ms 24976 KB Output is correct
66 Correct 1222 ms 29100 KB Output is correct
67 Correct 1515 ms 30508 KB Output is correct
68 Correct 1255 ms 29092 KB Output is correct
69 Correct 889 ms 28404 KB Output is correct
70 Correct 1432 ms 30520 KB Output is correct
71 Correct 1468 ms 30480 KB Output is correct
72 Correct 1476 ms 30464 KB Output is correct
73 Correct 1225 ms 28796 KB Output is correct
74 Correct 1235 ms 28768 KB Output is correct
75 Correct 1246 ms 29116 KB Output is correct
76 Correct 927 ms 28576 KB Output is correct
77 Correct 920 ms 28592 KB Output is correct
78 Correct 914 ms 28452 KB Output is correct
79 Correct 764 ms 27252 KB Output is correct
80 Correct 746 ms 27264 KB Output is correct
81 Correct 742 ms 27048 KB Output is correct
82 Correct 742 ms 29044 KB Output is correct
83 Correct 741 ms 29052 KB Output is correct
84 Correct 747 ms 28848 KB Output is correct
85 Correct 1787 ms 30948 KB Output is correct
86 Correct 176 ms 6624 KB Output is correct
87 Correct 119 ms 8032 KB Output is correct
88 Correct 1085 ms 31316 KB Output is correct
89 Correct 1756 ms 31072 KB Output is correct
90 Correct 1092 ms 31112 KB Output is correct
91 Correct 1277 ms 28880 KB Output is correct
92 Correct 1268 ms 28852 KB Output is correct
93 Correct 1871 ms 30224 KB Output is correct
94 Correct 1509 ms 30524 KB Output is correct
95 Correct 1484 ms 30452 KB Output is correct
96 Correct 1798 ms 31960 KB Output is correct
97 Correct 800 ms 27716 KB Output is correct
98 Correct 868 ms 30828 KB Output is correct
99 Correct 1791 ms 31352 KB Output is correct
100 Correct 1783 ms 31036 KB Output is correct
101 Correct 1845 ms 31296 KB Output is correct
102 Correct 1805 ms 31372 KB Output is correct
103 Correct 1963 ms 32200 KB Output is correct
104 Correct 1940 ms 32252 KB Output is correct
105 Correct 1440 ms 32020 KB Output is correct
106 Correct 1182 ms 31664 KB Output is correct
107 Correct 1341 ms 28808 KB Output is correct
108 Correct 1860 ms 31156 KB Output is correct
109 Correct 1357 ms 28904 KB Output is correct