제출 #261886

#제출 시각아이디문제언어결과실행 시간메모리
261886islingr다리 (APIO19_bridges)C++17
27 / 100
3077 ms15524 KiB
#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];
list<int> changed_edges, ord;

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); ord.sort(cmp);

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

		rep(i, l, r)
			if (t[i]) queries.eb(c[i], b[i], i);
			else changed[b[i]] = true;

        for (auto it = begin(ord); it != end(ord); )
            if (changed[*it]) {
                int e = *it;
                weights[e] = {{w[e], 0}};
                changed_edges.eb(e);
                it = ord.erase(it);
             } else ++it;

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

		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];
		changed_edges.sort(cmp);
		ord.merge(changed_edges);
	}
	rep(i, 0, q) if (t[i]) cout << ans[i] << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...