제출 #1210615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210615		dubabuba	다리 (APIO19_bridges)	C++17	14 / 100	2167 ms	5208 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 = 1e5 + 10;
int BLOCK_sz = 550;
int n, m, q, weight[mxn];
vector<pii> edges(mxn);
vector<pii> query(mxn);
bool changed[mxn];
int type[mxn];
int ans[mxn];

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) {
		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_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 main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> edges[i].ff >> edges[i].ss >> weight[i];
	}

	cin >> q;
	for(int i = 0; i < q; i++) {
		cin >> type[i] >> query[i].ff >> query[i].ss;
	}

	function<void(int)> connect = [&](int i) { DSU::unite(edges[i].ff, edges[i].ss); }; // i - edge ID
	if(n <= 1000 && m <= 1000 && q <= 1000)
		BLOCK_sz = 1;

	for(int L = 0; L < q; L += BLOCK_sz) {
		int R = min(L + BLOCK_sz, q);
		for(int i = 1; i <= m; i++)
			changed[i] = 0;

		vector<int> ask;
		for(int i = L; i < R; i++) {
			int x = query[i].ff; // edge ID or node
			int w = query[i].ss;
			if(type[i] == 1) {
				changed[x] = 1;
			}
			else {
				ask.push_back(i);
			}
		}

		vector<int> UC;
		for(int i = 1; i <= m; i++) {
			if(!changed[i])
				UC.push_back(i);
		}

		sort(ask.begin(), ask.end(), [&](int i, int j) { return query[i].ss > query[j].ss; }); // i, j - query ID
		sort(UC.begin(), UC.end(), [&](int i, int j) { return weight[i] > weight[j]; }); // i, j - edge ID

		DSU::clear(n);
		int ptr = 0;
		for(int i : ask) { // i - query ID
			const int u = query[i].ff;
			const int w = query[i].ss;

			while(ptr < UC.size()) {
				int e = UC[ptr];
				if(weight[e] < w) break;
				connect(e);
				ptr++;
			}

			const int snap = DSU::hist.size();
			for(int j = L; j < i; j++) {
				if(type[j] == 2) continue;
				int E = query[j].ff;
				int W = query[j].ss;

				if(W >= w) {
					connect(E); // sus
				}
			}

			for(int j = i + 1; j < R; j++) {
				if(type[j] == 2) continue;
				int E = query[j].ff;
				int W = weight[E];

				if(W >= w) {
					connect(E); // sus
				}
			}

			int p = DSU::parent(u);
			ans[i] = -DSU::par[p];
			DSU::roll_back(snap); // sus
		}

		for(int i = L; i < R; i++) {
			if(type[i] == 2) continue;
			int e = query[i].ff;
			int w = query[i].ss;
			weight[e] = w; // sus
		}

		// cout << L << ' ' << R << endl;
		// for(int i = 1; i <= m; i++)
		// 	cout << i << ": " << edges[i].ff << ' ' << edges[i].ss << " = " << weight[i] << " (" << changed[i] << ")\n";
	}

	for(int i = 0; i < q; i++) {
		if(type[i] == 2) {
			cout << ans[i] << endl;
		}
	}
}

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