Submission #562928

#	Time	Username	Problem	Language	Result	Execution time	Memory
562928		SeDunion	Bridges (APIO19_bridges)	C++17	100 / 100	2347 ms	17688 KiB

bridges

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,abm,fma,bmi2")
#include <iostream>
#include <cassert>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
	#include <bits/stdc++.h>
	#define cerr if(false)cerr
#endif
 
using namespace std;
using ll = long long;
 
const int N = 2e5 + 66;
 
/*
sqrt on queries:
 
used[i] -> which edges are presented in the block
 
for each block, let's do a kruskal without used edges
^ with queires in this block
 
1
2
3
4
5
---
6
7
8
9
10
11
----
12
13
14
15
*/
 
int p[N], sz[N];
int rb[N];
int rbsz;
 
int get(int x) {
	while (x != p[x]) x = p[x];
	return x;
}
 
void unite(int a, int b) {
	a = get(a), b = get(b);
	if (a == b) return;
	if (sz[a] > sz[b]) swap(a, b);
	rb[rbsz++] = a;
	p[a] = b;
	sz[b] += sz[a];
}
 
void rollback(int oo) {
	while (rbsz > oo) {
		int i = rb[--rbsz];
		sz[p[i]] -= sz[i];
		p[i] = i;
	}
}
 
int ea[N], eb[N], ec[N];
int qt[N], qx[N], qy[N];
 
vector<pair<int,int>>ev[N];
int ans[N];
const int K = 700;
 
int used[N];
 
vector<int>ed;
 
int curc[N];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int>all;
	for (int i = 1 ; i <= m ; ++ i) {
		cin >> ea[i] >> eb[i] >> ec[i];
		ec[i] = -ec[i];
		all.emplace_back(ec[i]);
	}
	int q;
	cin >> q;
	for (int i = 0 ; i < q ; ++ i) {
		cin >> qt[i] >> qx[i] >> qy[i];
		qy[i] = -qy[i];
		all.emplace_back(qy[i]);
	}
	sort(all.begin(), all.end());
	all.resize(unique(all.begin(), all.end()) - all.begin());
	for (int i = 1 ; i <= m ; ++ i) {
		ec[i] = lower_bound(all.begin(), all.end(), ec[i]) - all.begin();
	}
	for (int i = 0 ; i < q ; ++ i) {
		qy[i] = lower_bound(all.begin(), all.end(), qy[i]) - all.begin();
	}
	for (int l = 0 ; l < q ; l += K) {
		int r = min(q - 1, l + K - 1);
		for (int i = 1 ; i <= m ; ++ i) used[i] = 0;
		for (int i = l ; i <= r ; ++ i) {
			if (qt[i] == 1) used[qx[i]] = 1;
		}
		for (int i = 0 ; i < N ; ++ i) ev[i].clear();
      	rbsz = 0;
		for (int i = 1 ; i <= n ; ++ i) {
			p[i] = i, sz[i] = 1;
		}
		for (int i = 1 ; i <= m ; ++ i) if (!used[i]) {
			ev[ec[i]].emplace_back(-ea[i], eb[i]);
		}
		ed.clear();
		for (int i = l ; i <= r ; ++ i) {
			if (qt[i] == 2) {
				ev[qy[i]].emplace_back(qx[i], i);
			} else {
				ed.emplace_back(qx[i]);
			}
		}
		for (int tt = 0 ; tt < N ; ++ tt) {
		for (auto [a, b] : ev[tt]) {
			if (a < 0) {
				a = -a;
				unite(a, b);
			} else {
				int i = b;
				int oo = rbsz;
				for (int j : ed) curc[j] = ec[j];
				for (int j = l ; j < i ; ++ j) if (qt[j] == 1) curc[qx[j]] = qy[j];
				for (int j : ed) if (curc[j] <= qy[i]) unite(ea[j], eb[j]);
				ans[i] = sz[get(a)];
				rollback(oo);
			}
		}}
		for (int i = l ; i <= r ; ++ i) {
			if (qt[i] == 1) {
				ec[qx[i]] = qy[i];
			}
		}
	}
	for (int i = 0 ; i < q ; ++ i) {
		if (qt[i] == 2) 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