Submission #320059

#	Time	Username	Problem	Language	Result	Execution time	Memory
320059		kostia244	Bridges (APIO19_bridges)	C++17	29 / 100	3035 ms	6644 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;

int p[maxn], r[maxn], rb[maxn], rc;
void init() { fill(all(p), -1), fill(all(r), 1); rc = 0;}
int par(int v) { return p[v]!=-1 ? 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];
	rb[rc++] = j;
}
void rollback() {
	int x = rb[--rc];
	r[p[x]] -= r[x];
	p[x] = -1;
}
int used[maxn];
void solve(int L, int R) {
	for(int i = 0; i < m; i++) bkup[i] = w[i];
	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;//C.reserve(m);
	for(auto &i : eord) (used[i] ? B : A).push_back(i);
	int J = 0, bs;
	for(auto id : qs) {
		int s = x[id], mw = y[id];
		for(int j;J < A.size() && (j = A[J], w[j] <= mw); J++) {
			unite(u[j], v[j]);
		}
		bs = rc;
		for(int i = L; i < R; i++) if(t[i]^2) w[x[i]] = bkup[x[i]];
		for(int i = L; i < id; i++) if(t[i]^2) w[x[i]] = y[i];
		for(auto i : B) {
			if(w[i] <= mw) unite(u[i], v[i]);
		}
		ans[id] = r[par(s)];
		while(rc > bs) rollback();
	}
	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 = 220; 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:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int j;J < A.size() && (j = A[J], w[j] <= mw); J++) {
      |             ~~^~~~~~~~~~

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