제출 #1309155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309155		ppmn_6	다리 (APIO19_bridges)	C++20	100 / 100	1339 ms	3752 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int B = 1111;

struct DSU {
	int n;
	vector<int> p, sz;
	DSU(int n_) {
		init(n_);
	}
	void init(int n_) {
		n = n_;
		p.resize(n + 1);
		sz.resize(n + 1);
		iota(p.begin(), p.end(), 0);
		fill(sz.begin(), sz.end(), 1);
	}
	int root(int a) {
		if (p[a] != a) {
			return root(p[a]);
		}
		return a;
	}
	pair<int, int> join(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b) {
			return make_pair(0, 0);
		}
		if (sz[a] > sz[b]) {
			swap(a, b);
		}
		sz[b] += sz[a];
		p[a] = b;
		return make_pair(a, b);
	}
	void rollback(int a, int b) {
		sz[b] -= sz[a];
		p[a] = a;
	}
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m;
    vector<pair<int, int>> edges(m);
    vector<int> state(m);
    for (int i = 0; i < m; i++) {
		auto &[u, v] = edges[i];
		cin >> u >> v >> state[i];
	}
	cin >> q;
	vector<int> ans(q, 0);
	DSU dsu(n);
	for (int i = 0; i * B < q; i++) {
		vector<tuple<int, int, int>> queries;
		vector<int> ord, unchanged, ori = state, rb;
		vector<bool> changed(m, 0);
		dsu.init(n);
		for (int j = 0; j < B && i * B + j < q; j++) {
			int a, b, c;
			cin >> a >> b >> c;
			if (a == 1) {
				b--;
				changed[b] = 1;
			}
			else {
				ord.push_back(j);
			}
			queries.push_back({a, b, c});
		}
		sort(ord.begin(), ord.end(), [&](int x, int y){return get<2>(queries[x]) > get<2>(queries[y]);});
		for (int j = 0; j < m; j++) {
			if (!changed[j]) {
				unchanged.push_back(j);
			}
			else {
				rb.push_back(j);
			}
		}
		sort(unchanged.begin(), unchanged.end(), [&](int x, int y){return state[x] > state[y];});
		int p = 0;
		for (auto j : ord) {
			int lim = get<2>(queries[j]);
			if (p < unchanged.size()) {
				while (state[unchanged[p]] >= lim) {
					auto &[u, v] = edges[unchanged[p]];
					dsu.join(u, v);
					p++;
					if (p == unchanged.size()) {
						break;
					}
				}
			}
			for (int k = 0; k < j; k++) {
				auto &[t, b, r] = queries[k];
				if (t == 1) {
					state[b] = r;
				}
			}
			stack<pair<int, int>> st;
			for (auto k : rb) {
				if (state[k] >= lim) {
					auto &[u, v] = edges[k];
					st.push(dsu.join(u, v));
				}
			}
			ans[i * B + j] = dsu.sz[dsu.root(get<1>(queries[j]))];
			for (auto k : rb) {
				state[k] = ori[k];
			}
			while (st.size()) {
				auto [u, v] = st.top();
				st.pop();
				if (u) {
					dsu.rollback(u, v);
				}
			}
		}
		for (auto &[t, b, c] : queries) {
			if (t == 1) {
				state[b] = c;
			}
		}
	}
	for (auto i : ans) {
		if (i) {
			cout << i << "\n";
		}
	}
    

    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