Submission #633183

#	Time	Username	Problem	Language	Result	Execution time	Memory
633183		vovamr	Bridges (APIO19_bridges)	C++17	73 / 100	3059 ms	8628 KiB

bridges

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#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 + 10;
int p[N], rnk[N];
inline void build(int n) { for (int i = 0; i < n; ++i) p[i] = i, rnk[i] = 1; }
inline int par(int v) { if (p[v] == v) { return v; } return p[v] = par(p[v]); }
inline bool uni(int a, int b) {
	a = par(a), b = par(b);
	if (a == b) return 0;
	if (rnk[a] > rnk[b]) swap(a, b);
	p[a] = b, rnk[b] += rnk[a]; return 1;
}
 
inline void solve() {
	int n, m;
	cin >> n >> m;
 
	ve<array<int,3>> e(m);
	for (auto &[v, u, w] : e) cin >> v >> u >> w, --v, --u;
 
	int q;
	cin >> q;
	ve<array<int,3>> ar(q);
	for (auto &[t, a, b] : ar) {
		cin >> t >> a >> b;
		--a;
	}
 
	ve<int> res(q, -1);
 
	const int b = 580;
 
	ve<int> used(n);
	ve<ve<int>> gr(n);
 
	ve<int> changed(m);
	for (int l = 0; l < q; l += b) {
		int r = min(q - 1, l + b - 1);
 
		fill(all(changed), 0);
		for (int i = l; i <= r; ++i) {
			if (ar[i][0] == 1) {
				changed[ar[i][1]] = 1;
			}
		}
 
		ve<array<int,3>> edges;
		edges.reserve(m);
 
		for (int i = 0; i < m; ++i) {
			if (changed[i]) continue;
 
			auto &[v, u, w] = e[i];
			edges.pb({w, v, u});
		} sort(all(edges));
 
		ve<pair<array<int,3>,ve<array<int,3>>>> que;
		que.reserve(r - l + 1);
 
		for (int i = l; i <= r; ++i) {
			if (ar[i][0] == 1) {
				int id = ar[i][1];
				int x = ar[i][2];
				e[id][2] = x;
			}
			else {
				int s = ar[i][1], d = ar[i][2];
 
				que.pb({{-d,s,i}, {}});
				for (int j = l; j <= r; ++j) {
					if (ar[j][0] == 2) continue;
					int id = ar[j][1]; int w = e[id][2];
					if (w >= d) que.back().se.pb({e[id][0], e[id][1], w});
				}
			}
		}
 
		build(n);
		sort(all(que)); int p = sz(edges) - 1;
 
		for (auto &[_, vec] : que) {
			auto &[d, s, id] = _; d *= -1;
			while (~p && edges[p][0] >= d) {
				auto &[w, v, u] = edges[p];
				uni(v, u);
				--p;
			}
 
			for (auto &[v, u, w] : vec) {
				gr[par(v)].pb(par(u));
				gr[par(u)].pb(par(v));
			}
 
//			cout << id + 1 << ":" << '\n';
//			for (auto &[v, u, w] : vec) {
//				cout << v + 1 << " " << u + 1 << " " << w << '\n';
//			}
//			cout << '\n';
 
			int ans = 0;
			function<void(int)> dfs = [&gr,&used,&dfs,&ans](int v) {
				used[v] = 1; ans += rnk[v];
				for (auto &to : gr[v]) {
					if (used[to]) continue;
					dfs(to);
				}
			};
 
			dfs(par(s));
			res[id] = ans;
 
			used[par(s)] = 0;
			for (auto &[v, u, w] : vec) {
				gr[par(u)].clear();
				gr[par(v)].clear();
				used[par(v)] = used[par(u)] = 0;
			}
 
//			for (int i = 0; i < n; ++i) {
//				assert(!sz(gr[i]));
//				assert(!used[i]);
//			}
		}
	}
 
	for (int i = 0; i < q; ++i) if (~res[i]) cout << res[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 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27