Submission #562905

#TimeUsernameProblemLanguageResultExecution timeMemory
562905SeDunionBridges (APIO19_bridges)C++17
73 / 100
3076 ms20844 KiB
#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];
vector<tuple<int,int,int>>rb;

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.emplace_back(a, p[a], sz[a]);
	rb.emplace_back(b, p[b], sz[b]);
	p[a] = b;
	sz[b] += sz[a];
}

void rollback(int oo) {
	while ((int)rb.size() > oo) {
		auto [i, x, y] = rb.back();
		rb.pop_back();
		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 = 600;

int used[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();
		rb.clear();
		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]);
		}
		for (int i = l ; i <= r ; ++ i) {
			if (qt[i] == 2) {
				ev[qy[i]].emplace_back(qx[i], 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 = rb.size();
				for (int j = i - 1 ; j >= l ; -- j) {
					if (qt[j] == 1 && used[qx[j]] != 3 && qy[j] <= qy[i]) {
						unite(ea[qx[j]], eb[qx[j]]);
					}
					if (qt[j] == 1) used[qx[j]] = 3;
				}
				for (int j = l ; j <= r ; ++ j) {
					if (qt[j] == 1 && used[qx[j]] != 3 && ec[qx[j]] <= qy[i]) {
						unite(ea[qx[j]], eb[qx[j]]);
					}
				}
				ans[i] = sz[get(a)];
				rollback(oo);
				for (int j = l ; j <= r ; ++ j) {
					if (qt[j] == 1) {
						used[qx[j]] = 1;
					}
				}
			}
		}}
		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...