oj.uz

Submission #684821

# Submission time Handle Problem Language Result Execution time Memory
684821 2023-01-22T14:01:32 Z vovamr Bridges (APIO19_bridges) C++17
100 / 100
 1210 ms 13604 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
 
const int N = 5e4 + 100;
 
int pr[N], rnk[N];
inline void build(int n) {
	for (int i = 0; i < n; ++i) {
		pr[i] = i, rnk[i] = 1;
	}
}
inline int par(int v) {
	if (pr[v] == v) return v;
	return (pr[v] = par(pr[v]));
}
inline void uni(int a, int b) {
	a = par(a), b = par(b);
	if (a == b) return;
	if (rnk[a] > rnk[b]) swap(a, b);
	pr[a] = b, rnk[b] += rnk[a];
}
 
int bg = 0, en = 0;
int Qe[N];
 
int used[N];
ve<int> gr[N];
 
inline int bfs(int v) {
	int ans = 0;
	used[v] = 1; bg = en = 0;
	Qe[en++] = v;
	while (bg != en) {
		int v = Qe[bg++];
		ans += rnk[v];
		for (const auto &to : gr[v]) {
			if (used[to]) continue;
			used[to] = 1;
			Qe[en++] = to;
		}
	}
	return ans;
}
 
constexpr int b = 350;
 
const int M = 1e5 + 10;
const int Q = 1e5 + 10;
 
array<int,3> op[Q];
array<int,3> e[M];
 
array<int,3> que[Q]; int pq = 0;
ve<array<int,3>> edges[Q];

array<int,4> sorted_e[M], nch[M]; int p = 0;
 
bool used_in_block[M];
 
int ch[M]; int pc = 0;
array<int,4> nw[M]; int pn = 0;

array<int,4> result[M]; int prr = 0;

inline void upd() {
	pn = 0;
	for (int i = 0; i < pc; ++i) {
		const auto &[v, u, w] = e[ch[i]];
		nw[pn++] = {w, ch[i], v, u};
	}
	sort(nw, nw + pn);

	int pa = 0, pb = 0; prr = 0;
	while (pa < p || pb < pn) {
		if (pa == p) result[prr++] = nw[pb++];
		else if (pb == pn) result[prr++] = nch[pa++];
		else result[prr++] = (nw[pb] < nch[pa] ? nw[pb++] : nch[pa++]);
	}
	for (int i = 0; i < prr; ++i) sorted_e[i] = result[i];
}
 
inline void solve() {
	int n, m;
	cin >> n >> m;
 
	for (int i = 0; i < m; ++i) {
		int v, u, w;
		cin >> v >> u >> w, --v, --u;
		e[i] = {v, u, -w};
		sorted_e[i] = {-w, i, v, u};
	}
	sort(sorted_e, sorted_e + m);
 
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int t;
		cin >> t;
		if (t == 1) {
			int id, w;
			cin >> id >> w;
			op[i] = {1, --id, -w};
		}
		else {
			int v, w;
			cin >> v >> w;
			op[i] = {2, --v, -w};
		}
	}
 
	ve<int> answer(q, -1);
	for (int l = 0; l < q; l += b) {
 
		build(n);
		int r = min(q - 1, l + b - 1);
 
		for (int i = l; i <= r; ++i) {
			const auto &[type, a, b] = op[i];
			if (type == 1) used_in_block[a] = 1;
		}
 
		pc = p = 0;
		for (int i = 0; i < m; ++i) {
			if (used_in_block[i]) ch[pc++] = i;
			if (!used_in_block[sorted_e[i][1]]) {
				nch[p++] = sorted_e[i];
			}
		}
 
		pq = 0;
		for (int i = l; i <= r; ++i) {
			const auto &[type, a, b] = op[i];
			if (type == 2) {
				que[pq++] = {b, a, i};
				for (int j = 0; j < pc; ++j) if (e[ch[j]][2] <= b) edges[i].pb(e[ch[j]]);
			}
			else {
				e[a][2] = b;
			}
		}
 
		sort(que, que + pq);
 
		int ptr = 0;
		for (int id = 0; id < pq; ++id) {
			const auto &[w, v, i] = que[id];
			while (ptr < m && sorted_e[ptr][0] <= w) {
				if (!used_in_block[sorted_e[ptr][1]]) uni(sorted_e[ptr][2], sorted_e[ptr][3]);
				++ptr;
			}
 
			for (auto &[a, b, W] : edges[i]) {
				a = par(a), b = par(b);
				gr[a].pb(b);
				gr[b].pb(a);
			}
 
			answer[i] = bfs(par(v));
			used[par(v)] = 0;
 
			for (auto &[a, b, w] : edges[i]) {
				gr[a].clear();
				gr[b].clear();
				used[a] = used[b] = 0;
			}
		}
 
		for (int i = l; i <= r; ++i) {
			const auto &[type, a, b] = op[i];
			edges[i].clear();
			edges[i].shrink_to_fit();
			if (type == 1) used_in_block[a] = 0;
		}

		upd();
	}
 
	for (int i = 0; i < q; ++i) if (~answer[i]) cout << answer[i] << '\n';
}
 
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 21 ms 4452 KB Output is correct
4 Correct 5 ms 4052 KB Output is correct
5 Correct 15 ms 4260 KB Output is correct
6 Correct 14 ms 4224 KB Output is correct
7 Correct 17 ms 4272 KB Output is correct
8 Correct 15 ms 4180 KB Output is correct
9 Correct 21 ms 4308 KB Output is correct
10 Correct 17 ms 4364 KB Output is correct
11 Correct 16 ms 4236 KB Output is correct
12 Correct 17 ms 4268 KB Output is correct
13 Correct 21 ms 4292 KB Output is correct
14 Correct 19 ms 4264 KB Output is correct
15 Correct 17 ms 4180 KB Output is correct
16 Correct 18 ms 4316 KB Output is correct
17 Correct 17 ms 4180 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 10788 KB Output is correct
2 Correct 695 ms 10792 KB Output is correct
3 Correct 702 ms 10776 KB Output is correct
4 Correct 657 ms 10680 KB Output is correct
5 Correct 668 ms 10700 KB Output is correct
6 Correct 857 ms 9952 KB Output is correct
7 Correct 821 ms 9872 KB Output is correct
8 Correct 813 ms 9880 KB Output is correct
9 Correct 33 ms 5676 KB Output is correct
10 Correct 661 ms 10932 KB Output is correct
11 Correct 648 ms 10820 KB Output is correct
12 Correct 605 ms 9780 KB Output is correct
13 Correct 569 ms 9700 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 9244 KB Output is correct
2 Correct 379 ms 6988 KB Output is correct
3 Correct 586 ms 9352 KB Output is correct
4 Correct 530 ms 9292 KB Output is correct
5 Correct 32 ms 5588 KB Output is correct
6 Correct 568 ms 9216 KB Output is correct
7 Correct 521 ms 9144 KB Output is correct
8 Correct 463 ms 9000 KB Output is correct
9 Correct 380 ms 8664 KB Output is correct
10 Correct 381 ms 8652 KB Output is correct
11 Correct 415 ms 8992 KB Output is correct
12 Correct 377 ms 8932 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 12288 KB Output is correct
2 Correct 33 ms 5580 KB Output is correct
3 Correct 63 ms 9900 KB Output is correct
4 Correct 64 ms 9932 KB Output is correct
5 Correct 687 ms 12316 KB Output is correct
6 Correct 797 ms 12332 KB Output is correct
7 Correct 677 ms 12284 KB Output is correct
8 Correct 472 ms 9184 KB Output is correct
9 Correct 461 ms 9208 KB Output is correct
10 Correct 462 ms 9304 KB Output is correct
11 Correct 727 ms 10692 KB Output is correct
12 Correct 657 ms 10700 KB Output is correct
13 Correct 724 ms 10828 KB Output is correct
14 Correct 671 ms 12412 KB Output is correct
15 Correct 717 ms 12336 KB Output is correct
16 Correct 868 ms 12240 KB Output is correct
17 Correct 861 ms 12232 KB Output is correct
18 Correct 826 ms 12260 KB Output is correct
19 Correct 814 ms 12364 KB Output is correct
20 Correct 783 ms 11456 KB Output is correct
21 Correct 810 ms 11468 KB Output is correct
22 Correct 806 ms 12092 KB Output is correct
23 Correct 713 ms 11216 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 10788 KB Output is correct
2 Correct 695 ms 10792 KB Output is correct
3 Correct 702 ms 10776 KB Output is correct
4 Correct 657 ms 10680 KB Output is correct
5 Correct 668 ms 10700 KB Output is correct
6 Correct 857 ms 9952 KB Output is correct
7 Correct 821 ms 9872 KB Output is correct
8 Correct 813 ms 9880 KB Output is correct
9 Correct 33 ms 5676 KB Output is correct
10 Correct 661 ms 10932 KB Output is correct
11 Correct 648 ms 10820 KB Output is correct
12 Correct 605 ms 9780 KB Output is correct
13 Correct 569 ms 9700 KB Output is correct
14 Correct 550 ms 9244 KB Output is correct
15 Correct 379 ms 6988 KB Output is correct
16 Correct 586 ms 9352 KB Output is correct
17 Correct 530 ms 9292 KB Output is correct
18 Correct 32 ms 5588 KB Output is correct
19 Correct 568 ms 9216 KB Output is correct
20 Correct 521 ms 9144 KB Output is correct
21 Correct 463 ms 9000 KB Output is correct
22 Correct 380 ms 8664 KB Output is correct
23 Correct 381 ms 8652 KB Output is correct
24 Correct 415 ms 8992 KB Output is correct
25 Correct 377 ms 8932 KB Output is correct
26 Correct 754 ms 10692 KB Output is correct
27 Correct 834 ms 11012 KB Output is correct
28 Correct 751 ms 10740 KB Output is correct
29 Correct 595 ms 10356 KB Output is correct
30 Correct 856 ms 10756 KB Output is correct
31 Correct 886 ms 10844 KB Output is correct
32 Correct 863 ms 10892 KB Output is correct
33 Correct 767 ms 10700 KB Output is correct
34 Correct 788 ms 10756 KB Output is correct
35 Correct 741 ms 10656 KB Output is correct
36 Correct 630 ms 10520 KB Output is correct
37 Correct 606 ms 10480 KB Output is correct
38 Correct 596 ms 10672 KB Output is correct
39 Correct 519 ms 9804 KB Output is correct
40 Correct 538 ms 9800 KB Output is correct
41 Correct 500 ms 9828 KB Output is correct
42 Correct 489 ms 10432 KB Output is correct
43 Correct 488 ms 10444 KB Output is correct
44 Correct 477 ms 10440 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 21 ms 4452 KB Output is correct
4 Correct 5 ms 4052 KB Output is correct
5 Correct 15 ms 4260 KB Output is correct
6 Correct 14 ms 4224 KB Output is correct
7 Correct 17 ms 4272 KB Output is correct
8 Correct 15 ms 4180 KB Output is correct
9 Correct 21 ms 4308 KB Output is correct
10 Correct 17 ms 4364 KB Output is correct
11 Correct 16 ms 4236 KB Output is correct
12 Correct 17 ms 4268 KB Output is correct
13 Correct 21 ms 4292 KB Output is correct
14 Correct 19 ms 4264 KB Output is correct
15 Correct 17 ms 4180 KB Output is correct
16 Correct 18 ms 4316 KB Output is correct
17 Correct 17 ms 4180 KB Output is correct
18 Correct 687 ms 10788 KB Output is correct
19 Correct 695 ms 10792 KB Output is correct
20 Correct 702 ms 10776 KB Output is correct
21 Correct 657 ms 10680 KB Output is correct
22 Correct 668 ms 10700 KB Output is correct
23 Correct 857 ms 9952 KB Output is correct
24 Correct 821 ms 9872 KB Output is correct
25 Correct 813 ms 9880 KB Output is correct
26 Correct 33 ms 5676 KB Output is correct
27 Correct 661 ms 10932 KB Output is correct
28 Correct 648 ms 10820 KB Output is correct
29 Correct 605 ms 9780 KB Output is correct
30 Correct 569 ms 9700 KB Output is correct
31 Correct 550 ms 9244 KB Output is correct
32 Correct 379 ms 6988 KB Output is correct
33 Correct 586 ms 9352 KB Output is correct
34 Correct 530 ms 9292 KB Output is correct
35 Correct 32 ms 5588 KB Output is correct
36 Correct 568 ms 9216 KB Output is correct
37 Correct 521 ms 9144 KB Output is correct
38 Correct 463 ms 9000 KB Output is correct
39 Correct 380 ms 8664 KB Output is correct
40 Correct 381 ms 8652 KB Output is correct
41 Correct 415 ms 8992 KB Output is correct
42 Correct 377 ms 8932 KB Output is correct
43 Correct 722 ms 12288 KB Output is correct
44 Correct 33 ms 5580 KB Output is correct
45 Correct 63 ms 9900 KB Output is correct
46 Correct 64 ms 9932 KB Output is correct
47 Correct 687 ms 12316 KB Output is correct
48 Correct 797 ms 12332 KB Output is correct
49 Correct 677 ms 12284 KB Output is correct
50 Correct 472 ms 9184 KB Output is correct
51 Correct 461 ms 9208 KB Output is correct
52 Correct 462 ms 9304 KB Output is correct
53 Correct 727 ms 10692 KB Output is correct
54 Correct 657 ms 10700 KB Output is correct
55 Correct 724 ms 10828 KB Output is correct
56 Correct 671 ms 12412 KB Output is correct
57 Correct 717 ms 12336 KB Output is correct
58 Correct 868 ms 12240 KB Output is correct
59 Correct 861 ms 12232 KB Output is correct
60 Correct 826 ms 12260 KB Output is correct
61 Correct 814 ms 12364 KB Output is correct
62 Correct 783 ms 11456 KB Output is correct
63 Correct 810 ms 11468 KB Output is correct
64 Correct 806 ms 12092 KB Output is correct
65 Correct 713 ms 11216 KB Output is correct
66 Correct 754 ms 10692 KB Output is correct
67 Correct 834 ms 11012 KB Output is correct
68 Correct 751 ms 10740 KB Output is correct
69 Correct 595 ms 10356 KB Output is correct
70 Correct 856 ms 10756 KB Output is correct
71 Correct 886 ms 10844 KB Output is correct
72 Correct 863 ms 10892 KB Output is correct
73 Correct 767 ms 10700 KB Output is correct
74 Correct 788 ms 10756 KB Output is correct
75 Correct 741 ms 10656 KB Output is correct
76 Correct 630 ms 10520 KB Output is correct
77 Correct 606 ms 10480 KB Output is correct
78 Correct 596 ms 10672 KB Output is correct
79 Correct 519 ms 9804 KB Output is correct
80 Correct 538 ms 9800 KB Output is correct
81 Correct 500 ms 9828 KB Output is correct
82 Correct 489 ms 10432 KB Output is correct
83 Correct 488 ms 10444 KB Output is correct
84 Correct 477 ms 10440 KB Output is correct
85 Correct 1008 ms 13432 KB Output is correct
86 Correct 86 ms 10316 KB Output is correct
87 Correct 95 ms 10572 KB Output is correct
88 Correct 967 ms 13488 KB Output is correct
89 Correct 994 ms 13604 KB Output is correct
90 Correct 1053 ms 13172 KB Output is correct
91 Correct 763 ms 10660 KB Output is correct
92 Correct 771 ms 10720 KB Output is correct
93 Correct 916 ms 10104 KB Output is correct
94 Correct 1016 ms 12196 KB Output is correct
95 Correct 1030 ms 12400 KB Output is correct
96 Correct 1062 ms 11520 KB Output is correct
97 Correct 867 ms 12860 KB Output is correct
98 Correct 848 ms 12988 KB Output is correct
99 Correct 1127 ms 13464 KB Output is correct
100 Correct 1210 ms 13484 KB Output is correct
101 Correct 1095 ms 13436 KB Output is correct
102 Correct 1187 ms 13492 KB Output is correct
103 Correct 1110 ms 11932 KB Output is correct
104 Correct 1098 ms 11968 KB Output is correct
105 Correct 961 ms 11640 KB Output is correct
106 Correct 792 ms 11176 KB Output is correct
107 Correct 937 ms 11696 KB Output is correct
108 Correct 1147 ms 12848 KB Output is correct
109 Correct 1016 ms 11648 KB Output is correct