제출 #562720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
562720		SeDunion	Bridges (APIO19_bridges)	C++17	59 / 100	3076 ms	7004 KiB

bridges

#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 = 1e6 + 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<tuple<int,int,int>>ev;
int ans[N];
const int K = 350;

int used[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1 ; i <= m ; ++ i) {
		cin >> ea[i] >> eb[i] >> ec[i];
		ec[i] = -ec[i];
	}
	int q;
	cin >> q;
	for (int i = 0 ; i < q ; ++ i) {
		cin >> qt[i] >> qx[i] >> qy[i];
		qy[i] = -qy[i];
	}
	for (int i = 1 ; i <= n ; ++ i) {
		p[i] = i, sz[i] = 1;
	}
	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;
		}
		ev.clear();
		for (int i = 1 ; i <= m ; ++ i) if (!used[i]) {
			ev.emplace_back(ec[i], -ea[i], eb[i]);
		}
		for (int i = l ; i <= r ; ++ i) {
			if (qt[i] == 2) {
				ev.emplace_back(qy[i], qx[i], i);
			}
		}
		sort(ev.begin(), ev.end());
		rollback(0);
		for (auto [ignore, a, b] : ev) {
			if (a < 0) {
				a = -a;
				unite(a, b);
				cerr << a << " " << b << endl;
			} 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";
	}
}

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