Submission #260456

#	Time	Username	Problem	Language	Result	Execution time	Memory
260456		islingr	Bridges (APIO19_bridges)	C++17	100 / 100	2550 ms	11332 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];
int head(int u) { return nxt[u] < 0 ? u : nxt[u] = head(nxt[u]); }
void unite(int u, int v) {
	u = head(u); v = head(v);
	if (u == v) return;
	if (sz[u] > sz[v]) swap(u, v);
	nxt[u] = v; sz[v] += sz[u];
}

int u[M], v[M], w[M], ord[M];
short t[Q]; int b[Q], c[Q], ans[Q];
bool changed[M];
vector<int> changed_edges, changed_nodes, g[N];
vector<tuple<int, int, int>> queries;
vector<pair<int, int>> weights[M];
bool vis[N];

void dfs(int u) { vis[u] = 1; for (int v : g[u]) if (!vis[v]) dfs(v); }

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], ord[e] = 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();
		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; }

			for (auto e : changed_edges) {
				int c = 0;
				while (c < sz(weights[e]) && weights[e][c].second <= t) ++c;
				if (z <= weights[e][--c].first) {
					int x = head(u[e]), y = head(v[e]);
					g[x].eb(y); g[y].eb(x);
					changed_nodes.eb(x); changed_nodes.eb(y);
				}
			}

			dfs(s = head(s)); vis[s] = 0; ans[t] = sz[s];
			for (int x : changed_nodes) {
				if (vis[x]) ans[t] += sz[x];
				g[x].clear(), vis[x] = 0;
			}
			changed_nodes.clear();
		}

		rep(i, l, r) if (!t[i]) w[b[i]] = c[i];
	}
	rep(i, 0, q) if (t[i]) cout << ans[i] << '\n';
}

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