Submission #1180378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180378		trvhung	Bridges (APIO19_bridges)	C++20	100 / 100	1542 ms	11516 KiB

bridges

#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #define   ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const int N = 5e4 + 5;
const int M = 1e5 + 5;
const int S = 1000;
int n, m, q, u[M], v[M], w[M], t[M], x[M], y[M], ans[M];
bool changed[M];
vector<int> to_join[S];

struct dsu {

	int cnt;
	vector<int> root, sz;
	vector<pair<int &, int>> history;

	dsu(int n) : root(n + 1), sz(n + 1) {}

	void init() {
		cnt = n; history.clear();
		for (int i = 1; i <= n; ++i)
			root[i] = i, sz[i] = 1;
	}

	int find(int x) {
		return (root[x] == x) ? x : find(root[x]);
	}

	void unite(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return;
		if (sz[u] < sz[v]) swap(u, v);

		history.pb({root[v], root[v]});
		history.pb({sz[u], sz[u]});
		history.pb({cnt, cnt});

		root[v] = u; sz[u] += sz[v]; cnt--;
	}	

	int snapshot() {
		return history.size();
	}

	void rollback(int until) {
		while (snapshot() > until) {
			history.back().F = history.back().S;
			history.pop_back();
		}
	} 

};

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; ++i)
		cin >> u[i] >> v[i] >> w[i];
	cin >> q;
	for (int i = 1; i <= q; ++i)
		cin >> t[i] >> x[i] >> y[i];

	dsu dsu(n);

	for (int l = 1; l <= q; l += S) {
		int r = min(q, l + S - 1);
		dsu.init();
		fill(changed + 1, changed + 1 + m, false);

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

		for (int i = 1; i <= m; ++i)
			if (!changed[i])
				unchanged.push_back(i);

		for (int i = l; i <= r; ++i)
			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 < (int) unchanged.size() && w[unchanged[ptr]] >= y[i]) {
				dsu.unite(u[unchanged[ptr]], v[unchanged[ptr]]);
				ptr++;
			}
			int prev_size = dsu.snapshot();
			for (int j: to_join[i - l]) dsu.unite(u[j], v[j]);
			ans[i] = dsu.sz[dsu.find(x[i])];
			dsu.rollback(prev_size);
		}
	}

	for (int i = 1; i <= q; ++i)
		if (t[i] == 2)
			cout << ans[i] << el;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (!MULTI) solve();
    else {
        int test; cin >> test;
        while (test--) solve();
    }
    
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27