Submission #348827

#	Time	Username	Problem	Language	Result	Execution time	Memory
348827		denkendoemeer	Bridges (APIO19_bridges)	C++14	100 / 100	2756 ms	49880 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define eb(x...) emplace_back(x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) int((x).size())
 
const int N = 1 << 16, 	M = 1 << 17, Q = M, B = 1 << 10;
 
int nxt[N], sz[N]; stack<int> save;
int head(int u) { return nxt[u] < 0 ? u : head(nxt[u]); }
void unite(int u, int v) {
	u = head(u); v = head(v);
	if (u == v) return save.push(-1);
	if (sz[u] > sz[v]) swap(u, v);
	nxt[u] = v; sz[v] += sz[u]; save.push(u);
}
void rollback() {
	int u = save.top(); save.pop();
	if (u < 0) return;
	sz[nxt[u]] -= sz[u]; nxt[u] = -1;
}
 
int u[M], v[M], w[M], ord[M];
short t[Q]; int b[Q], c[Q];
 
int ans[Q];
 
bool changed[M];
vector<int> changed_edges;
vector<tuple<int, int, int>> queries;
vector<pair<int, int>> weights[M];
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, m;
	cin >> n >> m;
	rep(e, 0, m) cin >> u[e] >> v[e] >> w[e], --u[e], --v[e];
 
	int q; cin >> q;
	rep(i, 0, q) cin >> t[i] >> b[i] >> c[i], --b[i], --t[i];
 
	for (int l = 0, r = 0; r = min(l + B, q), l < q; l += B) {
		fill(nxt, nxt + n, -1); fill(sz, sz + n, 1);
		fill(changed, changed + m, false); changed_edges.clear();
		queries.clear();
		iota(ord, ord + m, 0); sort(ord, ord + m, [&](int x, int y) { return w[x] > w[y]; });
 
		rep(i, l, r)
			if (t[i]) queries.eb(c[i], b[i], i);
			else changed[b[i]] = true;
		
		rep(e, 0, m) if (changed[e]) weights[e] = {{w[e], 0}}, changed_edges.eb(e);
		rep(i, l, r) if (!t[i]) weights[b[i]].eb(c[i], i);
		sort(rall(queries));
 
		int e = 0;
		for (auto &[z, s, t] : queries) {
			while (e < m && z <= w[ord[e]]) { if (!changed[ord[e]]) unite(u[ord[e]], v[ord[e]]); ++e; }
			int dsu_changes = 0;
			for (auto e : changed_edges) {
				int c = 0;
				while (c < sz(weights[e]) && weights[e][c].second <= t) ++c;
				--c; if (z <= weights[e][c].first) unite(u[e], v[e]), ++dsu_changes;
			}
			ans[t] = sz[head(s)];
			while (dsu_changes--) rollback();
		}
		
		rep(i, l, r) if (!t[i]) w[b[i]] = c[i];
	}
	rep(i, 0, q) if (t[i]) cout << ans[i] << '\n';
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |   for (auto &[z, s, t] : queries) {
      |              ^

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