Submission #266462

#	Time	Username	Problem	Language	Result	Execution time	Memory
266462		islingr	Bridges (APIO19_bridges)	C++17	14 / 100	568 ms	18152 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];
short t[Q]; int b[Q], c[Q], ans[Q];
bool changed[M];
vector<int> changed_nodes, g[N];
vector<tuple<int, int, int>> queries;
vector<pair<int, int>> weights[M];
bool vis[N];
vector<int> ord, changed_edges, tmp;

void dfs(int u) { vis[u] = 1; for (int v : g[u]) if (!vis[v]) dfs(v); }
bool cmp(int x, int y) { return w[x] > w[y]; }

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.resize(m); iota(all(ord), 0); sort(all(ord), cmp);
	tmp.resize(m);

	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);
		queries.clear();

		rep(i, l, r)
			if (t[i]) queries.eb(c[i], b[i], i);
			else changed[b[i]] = true;
		sort(rall(queries));
		
		auto second = stable_partition(ord.begin(), ord.end(), [](int x) { return !changed[x]; });
		for_each(second, ord.end(), [](int x) {
			weights[x] = {{w[x], 0}};
			changed_edges.push_back(x);
		});
		ord.erase(second, ord.end());

		rep(i, l, r) if (!t[i]) weights[b[i]].eb(c[i], i);

		auto it = begin(ord);
		for (auto &[z, s, t] : queries) {
			while (it != end(ord) && z <= w[*it]) { unite(u[*it], v[*it]); ++it; }

			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];
		
		sort(all(changed_edges), cmp);
		merge(all(ord), all(changed_edges), begin(tmp), cmp);
		swap(ord, tmp);
	}
	rep(i, 0, q) if (t[i]) cout << ans[i] << '\n';
}

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