oj.uz

Submission #551013

# Submission time Handle Problem Language Result Execution time Memory
551013 2022-04-19T17:41:50 Z valerikk Bridges (APIO19_bridges) C++17
100 / 100
 2874 ms 10912 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 50057;
const int M = 100123;
const int B = 500;

int n, m;
int a[M], b[M], c[M];
int Q;
int t[M], x[M], y[M];

int dsu[N];
int sz[N];

vector<int> g[N];
bool used[N];

int ans[M];

int e[M];
bool inb[M];
bool was[M];
int q[N];

int get(int i) {
	return i == dsu[i] ? i : dsu[i] = get(dsu[i]);
}

void merge(int i, int j) {
	i = get(i);
	j = get(j);
	
	if (i == j) 
		return;

	if (sz[i] > sz[j]) 
		swap(i, j);

	sz[j] += sz[i];
	dsu[i] = j;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		cin >> a[i] >> b[i] >> c[i];
		--a[i];
		--b[i];
	}

	vector<int> ord(m);
	iota(ord.begin(), ord.end(), 0);
	sort(begin(ord), end(ord), [&](const int &i, const int &j) {
		return c[i] > c[j];
	});

	cin >> Q;
	for (int i = 0; i < Q; ++i) {
		cin >> t[i] >> x[i] >> y[i];
		--x[i];
	}

	for (int bl = 0; bl < Q; bl += B) {
		int br = min(Q, bl + B);

		for (int i = bl; i < br; ++i) {
			if (t[i] == 1) 
				inb[x[i]] = true;
		}

		int esz = 0;
		
		for (int i : ord) {
			if (!inb[i]) 
				e[esz++] = i;
		}

		vector<int> p;
		
		for (int i = bl; i < br; ++i) {
			if (t[i] == 2) 
				p.push_back(i);
		}

		sort(begin(p), end(p), [&](const int &i, const int &j) {
			return y[i] > y[j];
		});

		for (int i = 0; i < n; ++i) {
			dsu[i] = i;
			sz[i] = 1;
		}

		int eptr = 0;

		for (int i : p) {
			while (eptr < esz && c[e[eptr]] >= y[i]) {
				merge(a[e[eptr]], b[e[eptr]]);
				++eptr;
			}

			// cout << "i " << i << endl;
			for (int j = i - 1; j >= bl; --j) {
				if (t[j] == 1 && !was[x[j]]) {
					if (y[j] >= y[i]) {
						// cout << "add1 " << j << " " << a[x[j]] << " " << b[x[j]] << " " << y[j] << endl;
						g[get(a[x[j]])].emplace_back(get(b[x[j]]));
						g[get(b[x[j]])].emplace_back(get(a[x[j]]));
					}
					was[x[j]] = true;
				}
			}
			for (int j = br - 1; j > i; --j) {
				if (t[j] == 1 && !was[x[j]]) {
					if (c[x[j]] >= y[i]) {
						// cout << "add2 " << j << " " << x[j] << " " << a[x[j]] << " " << b[x[j]] << " " << c[x[j]] << endl;
						g[get(a[x[j]])].emplace_back(get(b[x[j]]));
						g[get(b[x[j]])].emplace_back(get(a[x[j]]));
					}
					was[x[j]] = true;
				}
			}

			int qh = 0, qt = 0;
			
			q[qt++] = get(x[i]);
			used[get(x[i])] = true;

			while (qh < qt) {
				int v = q[qh++];

				ans[i] += sz[v];

				for (int u : g[v]) {
					if (!used[u]) {
						used[u] = true;
						q[qt++] = u;
					}
				}
			}

			used[get(x[i])] = false;

			for (int j = i - 1; j >= bl; --j) {
				if (t[j] == 1 && was[x[j]]) {
					// if (y[j] >= y[i]) {
						// cout << "remove1 " << j << " " << a[x[j]] << " " << b[x[j]] << " " << y[j] << endl;
						used[get(a[x[j]])] = false;
						used[get(b[x[j]])] = false;
						g[get(a[x[j]])].clear();
						g[get(b[x[j]])].clear();
					// }
					was[x[j]] = false;
				}
			}
			for (int j = br - 1; j > i; --j) {
				if (t[j] == 1 && was[x[j]]) {
					// if (c[x[j]] >= y[i]) {
						// cout << "remove2 " << j << " " << a[x[j]] << " " << b[x[j]] << " " << c[x[j]] << endl;
						used[get(a[x[j]])] = false;
						used[get(b[x[j]])] = false;
						g[get(a[x[j]])].clear();
						g[get(b[x[j]])].clear();
					// }
					was[x[j]] = false;
				}
			}
		}

		for (int i = bl; i < br; ++i) {
			if (t[i] == 1) {
				inb[x[i]] = false;
				c[x[i]] = y[i];
			}
		}
		sort(ord.begin(), ord.end(), [&](const int &i, const int &j) {
			return c[i] > c[j];
		});
	}

	for (int i = 0; i < Q; ++i) {
		if (t[i] == 2) {
			cout << ans[i] << "\n";
		}
	}

	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 55 ms 1760 KB Output is correct
4 Correct 12 ms 1684 KB Output is correct
5 Correct 36 ms 1732 KB Output is correct
6 Correct 33 ms 1728 KB Output is correct
7 Correct 37 ms 1712 KB Output is correct
8 Correct 36 ms 1708 KB Output is correct
9 Correct 39 ms 1708 KB Output is correct
10 Correct 37 ms 1708 KB Output is correct
11 Correct 35 ms 1712 KB Output is correct
12 Correct 37 ms 1716 KB Output is correct
13 Correct 43 ms 1712 KB Output is correct
14 Correct 41 ms 1704 KB Output is correct
15 Correct 40 ms 1824 KB Output is correct
16 Correct 37 ms 1856 KB Output is correct
17 Correct 37 ms 1620 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1782 ms 5932 KB Output is correct
2 Correct 1727 ms 6036 KB Output is correct
3 Correct 1695 ms 6180 KB Output is correct
4 Correct 1742 ms 6168 KB Output is correct
5 Correct 1737 ms 5980 KB Output is correct
6 Correct 2166 ms 5336 KB Output is correct
7 Correct 2103 ms 5384 KB Output is correct
8 Correct 2093 ms 5240 KB Output is correct
9 Correct 99 ms 3196 KB Output is correct
10 Correct 1537 ms 6064 KB Output is correct
11 Correct 1449 ms 5980 KB Output is correct
12 Correct 1276 ms 5460 KB Output is correct
13 Correct 1226 ms 5384 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1465 ms 5428 KB Output is correct
2 Correct 1022 ms 3904 KB Output is correct
3 Correct 1627 ms 5384 KB Output is correct
4 Correct 1504 ms 5136 KB Output is correct
5 Correct 110 ms 3204 KB Output is correct
6 Correct 1583 ms 5048 KB Output is correct
7 Correct 1477 ms 5104 KB Output is correct
8 Correct 1366 ms 5164 KB Output is correct
9 Correct 989 ms 4768 KB Output is correct
10 Correct 941 ms 4772 KB Output is correct
11 Correct 965 ms 5064 KB Output is correct
12 Correct 889 ms 5140 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1408 ms 5884 KB Output is correct
2 Correct 123 ms 3224 KB Output is correct
3 Correct 132 ms 3644 KB Output is correct
4 Correct 88 ms 3620 KB Output is correct
5 Correct 1102 ms 5848 KB Output is correct
6 Correct 1389 ms 5848 KB Output is correct
7 Correct 1067 ms 5848 KB Output is correct
8 Correct 800 ms 4612 KB Output is correct
9 Correct 783 ms 4824 KB Output is correct
10 Correct 737 ms 4800 KB Output is correct
11 Correct 1064 ms 5272 KB Output is correct
12 Correct 1081 ms 5428 KB Output is correct
13 Correct 1059 ms 5404 KB Output is correct
14 Correct 860 ms 5964 KB Output is correct
15 Correct 877 ms 5964 KB Output is correct
16 Correct 1336 ms 5836 KB Output is correct
17 Correct 1337 ms 5864 KB Output is correct
18 Correct 1287 ms 5812 KB Output is correct
19 Correct 1269 ms 5956 KB Output is correct
20 Correct 1201 ms 5856 KB Output is correct
21 Correct 1185 ms 5904 KB Output is correct
22 Correct 1234 ms 6112 KB Output is correct
23 Correct 990 ms 6004 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1782 ms 5932 KB Output is correct
2 Correct 1727 ms 6036 KB Output is correct
3 Correct 1695 ms 6180 KB Output is correct
4 Correct 1742 ms 6168 KB Output is correct
5 Correct 1737 ms 5980 KB Output is correct
6 Correct 2166 ms 5336 KB Output is correct
7 Correct 2103 ms 5384 KB Output is correct
8 Correct 2093 ms 5240 KB Output is correct
9 Correct 99 ms 3196 KB Output is correct
10 Correct 1537 ms 6064 KB Output is correct
11 Correct 1449 ms 5980 KB Output is correct
12 Correct 1276 ms 5460 KB Output is correct
13 Correct 1226 ms 5384 KB Output is correct
14 Correct 1465 ms 5428 KB Output is correct
15 Correct 1022 ms 3904 KB Output is correct
16 Correct 1627 ms 5384 KB Output is correct
17 Correct 1504 ms 5136 KB Output is correct
18 Correct 110 ms 3204 KB Output is correct
19 Correct 1583 ms 5048 KB Output is correct
20 Correct 1477 ms 5104 KB Output is correct
21 Correct 1366 ms 5164 KB Output is correct
22 Correct 989 ms 4768 KB Output is correct
23 Correct 941 ms 4772 KB Output is correct
24 Correct 965 ms 5064 KB Output is correct
25 Correct 889 ms 5140 KB Output is correct
26 Correct 1900 ms 6248 KB Output is correct
27 Correct 1991 ms 6160 KB Output is correct
28 Correct 1882 ms 5996 KB Output is correct
29 Correct 1629 ms 6208 KB Output is correct
30 Correct 2095 ms 6188 KB Output is correct
31 Correct 2116 ms 6084 KB Output is correct
32 Correct 2082 ms 6356 KB Output is correct
33 Correct 1920 ms 6348 KB Output is correct
34 Correct 1911 ms 6056 KB Output is correct
35 Correct 1926 ms 6164 KB Output is correct
36 Correct 1667 ms 6120 KB Output is correct
37 Correct 1657 ms 6196 KB Output is correct
38 Correct 1633 ms 6112 KB Output is correct
39 Correct 1258 ms 5568 KB Output is correct
40 Correct 1226 ms 5552 KB Output is correct
41 Correct 1230 ms 5476 KB Output is correct
42 Correct 1128 ms 6296 KB Output is correct
43 Correct 1143 ms 6352 KB Output is correct
44 Correct 1139 ms 6216 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 55 ms 1760 KB Output is correct
4 Correct 12 ms 1684 KB Output is correct
5 Correct 36 ms 1732 KB Output is correct
6 Correct 33 ms 1728 KB Output is correct
7 Correct 37 ms 1712 KB Output is correct
8 Correct 36 ms 1708 KB Output is correct
9 Correct 39 ms 1708 KB Output is correct
10 Correct 37 ms 1708 KB Output is correct
11 Correct 35 ms 1712 KB Output is correct
12 Correct 37 ms 1716 KB Output is correct
13 Correct 43 ms 1712 KB Output is correct
14 Correct 41 ms 1704 KB Output is correct
15 Correct 40 ms 1824 KB Output is correct
16 Correct 37 ms 1856 KB Output is correct
17 Correct 37 ms 1620 KB Output is correct
18 Correct 1782 ms 5932 KB Output is correct
19 Correct 1727 ms 6036 KB Output is correct
20 Correct 1695 ms 6180 KB Output is correct
21 Correct 1742 ms 6168 KB Output is correct
22 Correct 1737 ms 5980 KB Output is correct
23 Correct 2166 ms 5336 KB Output is correct
24 Correct 2103 ms 5384 KB Output is correct
25 Correct 2093 ms 5240 KB Output is correct
26 Correct 99 ms 3196 KB Output is correct
27 Correct 1537 ms 6064 KB Output is correct
28 Correct 1449 ms 5980 KB Output is correct
29 Correct 1276 ms 5460 KB Output is correct
30 Correct 1226 ms 5384 KB Output is correct
31 Correct 1465 ms 5428 KB Output is correct
32 Correct 1022 ms 3904 KB Output is correct
33 Correct 1627 ms 5384 KB Output is correct
34 Correct 1504 ms 5136 KB Output is correct
35 Correct 110 ms 3204 KB Output is correct
36 Correct 1583 ms 5048 KB Output is correct
37 Correct 1477 ms 5104 KB Output is correct
38 Correct 1366 ms 5164 KB Output is correct
39 Correct 989 ms 4768 KB Output is correct
40 Correct 941 ms 4772 KB Output is correct
41 Correct 965 ms 5064 KB Output is correct
42 Correct 889 ms 5140 KB Output is correct
43 Correct 1408 ms 5884 KB Output is correct
44 Correct 123 ms 3224 KB Output is correct
45 Correct 132 ms 3644 KB Output is correct
46 Correct 88 ms 3620 KB Output is correct
47 Correct 1102 ms 5848 KB Output is correct
48 Correct 1389 ms 5848 KB Output is correct
49 Correct 1067 ms 5848 KB Output is correct
50 Correct 800 ms 4612 KB Output is correct
51 Correct 783 ms 4824 KB Output is correct
52 Correct 737 ms 4800 KB Output is correct
53 Correct 1064 ms 5272 KB Output is correct
54 Correct 1081 ms 5428 KB Output is correct
55 Correct 1059 ms 5404 KB Output is correct
56 Correct 860 ms 5964 KB Output is correct
57 Correct 877 ms 5964 KB Output is correct
58 Correct 1336 ms 5836 KB Output is correct
59 Correct 1337 ms 5864 KB Output is correct
60 Correct 1287 ms 5812 KB Output is correct
61 Correct 1269 ms 5956 KB Output is correct
62 Correct 1201 ms 5856 KB Output is correct
63 Correct 1185 ms 5904 KB Output is correct
64 Correct 1234 ms 6112 KB Output is correct
65 Correct 990 ms 6004 KB Output is correct
66 Correct 1900 ms 6248 KB Output is correct
67 Correct 1991 ms 6160 KB Output is correct
68 Correct 1882 ms 5996 KB Output is correct
69 Correct 1629 ms 6208 KB Output is correct
70 Correct 2095 ms 6188 KB Output is correct
71 Correct 2116 ms 6084 KB Output is correct
72 Correct 2082 ms 6356 KB Output is correct
73 Correct 1920 ms 6348 KB Output is correct
74 Correct 1911 ms 6056 KB Output is correct
75 Correct 1926 ms 6164 KB Output is correct
76 Correct 1667 ms 6120 KB Output is correct
77 Correct 1657 ms 6196 KB Output is correct
78 Correct 1633 ms 6112 KB Output is correct
79 Correct 1258 ms 5568 KB Output is correct
80 Correct 1226 ms 5552 KB Output is correct
81 Correct 1230 ms 5476 KB Output is correct
82 Correct 1128 ms 6296 KB Output is correct
83 Correct 1143 ms 6352 KB Output is correct
84 Correct 1139 ms 6216 KB Output is correct
85 Correct 2752 ms 7088 KB Output is correct
86 Correct 244 ms 5704 KB Output is correct
87 Correct 156 ms 5816 KB Output is correct
88 Correct 1766 ms 9164 KB Output is correct
89 Correct 2778 ms 10848 KB Output is correct
90 Correct 1747 ms 8864 KB Output is correct
91 Correct 1967 ms 8940 KB Output is correct
92 Correct 1920 ms 8860 KB Output is correct
93 Correct 2223 ms 7940 KB Output is correct
94 Correct 2381 ms 9788 KB Output is correct
95 Correct 2477 ms 10124 KB Output is correct
96 Correct 2467 ms 8732 KB Output is correct
97 Correct 1164 ms 8520 KB Output is correct
98 Correct 1241 ms 9020 KB Output is correct
99 Correct 2775 ms 10780 KB Output is correct
100 Correct 2797 ms 10608 KB Output is correct
101 Correct 2874 ms 10912 KB Output is correct
102 Correct 2856 ms 10764 KB Output is correct
103 Correct 2561 ms 8964 KB Output is correct
104 Correct 2556 ms 9204 KB Output is correct
105 Correct 1908 ms 9148 KB Output is correct
106 Correct 1535 ms 9200 KB Output is correct
107 Correct 1939 ms 8864 KB Output is correct
108 Correct 2709 ms 9620 KB Output is correct
109 Correct 1793 ms 7608 KB Output is correct