Submission #320079

#	Time	Username	Problem	Language	Result	Execution time	Memory
320079		kostia244	Bridges (APIO19_bridges)	C++17	100 / 100	2835 ms	11956 KiB

bridges

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,ssse3,sse4,sse4.1")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int maxn = 1<<17;
int n, m, q, u[maxn], v[maxn], w[maxn], t[maxn], x[maxn], y[maxn], ans[maxn], bkup[maxn];
vector<int> eord;
struct dsu {
	int p[maxn], r[maxn], sz[maxn];
	void init() { fill(all(p), -1), fill(all(r), 1); fill(all(sz), 0);}
	int par(int v) { return p[v]!=-1 ? p[v] = par(p[v]) : v; }
	void unite(int i, int j) {
		i = par(i), j = par(j);
		if(i == j) return;
		if(r[i] > r[j]) swap(i, j);
		p[j] = i, r[i] += r[j], sz[i] += sz[j];
	}
};
int used[maxn];
dsu d, g;
void solve(int L, int R) {
	for(int i = 0; i < m; i++) bkup[i] = w[i];
	d.init();
	fill(all(used), 0);
	vector<int> qs;
	for(int i = L; i < R; i++)
		if(t[i] == 1) used[x[i]] = maxn;
		else qs.push_back(i);
	sort(all(qs), [&](auto i, auto j) {  return y[i] < y[j]; });
	vector<int> A, B, C;
	A.reserve(m);
	B.reserve(R-L+1);
	C.reserve(m);
	for(auto &i : eord) (used[i] ? B : A).push_back(i);
	int J = 0;
	for(auto id : qs) {
		int s = x[id], mw = y[id];
		for(int j;J < A.size() && (j = A[J], w[j] <= mw); J++) {
			d.unite(u[j], v[j]);
		}
		for(auto i : B) w[i] = bkup[i];
		for(int i = L; i < id; i++) if(t[i]^2) w[x[i]] = y[i];
		for(auto i : B) {
			int X = d.par(u[i]), Y = d.par(v[i]);
			g.r[X] = g.r[Y] = 1;
			g.p[X] = g.p[Y] = -1;
			g.sz[X] = d.r[X];
			g.sz[Y] = d.r[Y];
		}
		s = d.par(s);
		g.r[s] = 1, g.p[s] = -1, g.sz[s] = d.r[s];
		for(auto i : B) {
			if(w[i] <= mw) g.unite(d.par(u[i]), d.par(v[i]));
		}
		ans[id] = g.sz[g.par(d.par(s))];
	}
	for(int i = L; i < R; i++)
		if(t[i]^2) w[x[i]] = y[i];
	auto cmp = [&](auto i, auto j) { return w[i] < w[j]; };
	sort(all(B), cmp);
	merge(all(A), all(B), back_inserter(C), cmp);
	eord = C;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	fill(all(ans), 0);
	cin >> n >> m;
	for(int i = 0; i < m; i++) cin >> u[i] >> v[i] >> w[i], u[i]--, v[i]--, w[i] *= -1;
	for(int i = (cin>>q, 0); i < q; i++) cin >> t[i] >> x[i] >> y[i], x[i]--, y[i] *= -1;
	eord.resize(m), iota(all(eord), 0);
	sort(all(eord), [&](auto i, auto j) { return w[i] < w[j]; });
	for(int i = 0, B = 700; i < q; i += B) solve(i, min(q, i+B));
	for(int i = 0; i < q; i++) if(ans[i] > 0) cout << ans[i] << '\n';
}

Compilation message (stderr)

bridges.cpp: In function 'void solve(int, int)':
bridges.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j;J < A.size() && (j = A[J], w[j] <= mw); J++) {
      |             ~~^~~~~~~~~~

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