Submission #1210600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210600		dubabuba	Bridges (APIO19_bridges)	C++17	0 / 100	3094 ms	5228 KiB

bridges

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

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 5e4 + 10;
const int BLOCK_sz = 340;

namespace DSU {
	int par[mxn];
	stack<pair<pii, pii>> hist;

	int parent(int u) { return par[u] < 0 ? u : parent(par[u]); }
	void unite(int u, int v) {
		// cout << "unite: " << u << ' ' << v << endl;
		u = parent(u);
		v = parent(v);
		if(u == v) return;

		if(par[u] > par[v]) swap(u, v);
		hist.push(MP(MP(u, par[u]), MP(v, par[v])));
		par[u] += par[v];
		par[v] = u;
	}
	void roll() {
		if(hist.empty()) return;
		int u, v, pu, pv;
		tie(u, pu) = hist.top().ff;
		tie(v, pv) = hist.top().ss;

		par[u] = pu;
		par[v] = pv;
		hist.pop();
	}
	void roll_back(int sz) {
		while(hist.size() > sz) {
			int u, pu, v, pv;
			tie(u, pu) = hist.top().ff;
			tie(v, pv) = hist.top().ss;

			par[u] = pu;
			par[v] = pv;
			hist.pop();
		}
	}

	void clear(int n) {
		memset(par, -1, sizeof(int) * (n + 5));
		while(hist.size()) hist.pop();
	}
};

int n, m, q, weight[mxn * 2];
vector<pair<pii, int>> edges;
vector<pair<int, pii>> query;
bitset<mxn * 2> changed;

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		edges.emplace_back(MP(u, v), w);
		weight[i] = w;
	}

	cin >> q;
	for(int i = 0; i < q; i++) {
		int t, x, w;
		cin >> t >> x >> w;
		if(t == 1) x--;
		query.emplace_back(t, MP(x, w));
	}

	// for(int i = 0; i < m; i++)
	// 	cout << i << " = " << edges[i].ff.ff << ' ' << edges[i].ff.ss << endl;

	for(int L = 0; L < q; L += BLOCK_sz) {
		int R = min(L + BLOCK_sz, q) - 1;
		// cout << L << ' ' << R << endl;
		assert(L <= R);

		changed = 0;
		for(int i = L; i <= R; i++) {
			int t = query[i].ff, x, w;
			tie(x, w) = query[i].ss;

			if(t == 1) {
				changed[x] = 1;
				// cout << "change " << x << endl;
			}
		}

		vector<int> UC, CH;
		for(int i = 0; i < m; i++)
			if(!changed[i])
				UC.push_back(i);
			else
				CH.push_back(i);

		sort(UC.begin(), UC.end(), [&](int i, int j) -> bool { return weight[i] > weight[j]; });
		sort(CH.begin(), CH.end(), [&](int i, int j) -> bool { return weight[i] > weight[j]; });

		// cout << "UC = ";
		// for(int i : UC)
		// 	cout << i << ' ';
		// cout << endl;

		// cout << "CH = ";
		// for(int i : CH)
		// 	cout << i << ' ';
		// cout << endl;

		// cout << "\n\n" << "DSU:\n";

		DSU::clear(n);
		int ptr = 0;
		for(int i = L; i <= R; i++) {
			int t = query[i].ff;
			int x, w;
			tie(x, w) = query[i].ss;

			if(t == 1) {
				weight[x] = w;
				sort(CH.begin(), CH.end(), [&](int i, int j) -> bool { return weight[i] > weight[j]; });
				continue;
			}

			// cout << " ptr = " << ptr << ", weight " << UC[ptr] << " = " << weight[UC[ptr]] << endl;
			while(ptr < UC.size() && weight[UC[ptr]] >= w) {
				// cout << "unchanged " << UC[ptr] << ": " << weight[UC[ptr]] << endl;

				int e = UC[ptr];
				DSU::unite(edges[e].ff.ff, edges[e].ff.ss);
				ptr++;
			}

			while(0 < ptr && weight[UC[ptr - 1]] < w) {
				ptr--;
				DSU::roll();
			}

			int snap = DSU::hist.size();
			for(int x : CH) {
				// cout << "changed " << x << ": " << weight[x] << endl;
				if(weight[x] >= w)
					DSU::unite(edges[x].ff.ff, edges[x].ff.ss);
			}

			int p = DSU::parent(x);

			// cout << "from " << x << " = (" << w << ") ";
			cout << -DSU::par[p] << endl;
			DSU::roll_back(snap);
		}
	}
	return 0;
}

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