Submission #562925

#TimeUsernameProblemLanguageResultExecution timeMemory
562925SeDunion다리 (APIO19_bridges)C++17
73 / 100
3035 ms21088 KiB
#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];
tuple<int,int,int>rb[N];
int rbsz;
 
int get(int x) {
	if (x == p[x]) return x;
	return get(p[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], sz[a]};
	rb[rbsz++] = {b, p[b], sz[b]};
	p[a] = b;
	sz[b] += sz[a];
}
 
void rollback(int oo) {
	while (rbsz > oo) {
		auto [i, x, y] = rb[--rbsz];
		p[i] = x, sz[i] = y;
	}
}
 
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];
 
int ed[N], edsz;
 
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]);
		}
		edsz = 0;
		for (int i = l ; i <= r ; ++ i) {
			if (qt[i] == 2) {
				ev[qy[i]].emplace_back(qx[i], i);
			} else {
				ed[edsz++] = 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 _ = 0 ; _ < edsz ; ++ _) {
					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 _ = 0 ; _ < edsz ; ++ _) {
					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";
	}
}
#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...