Submission #1208787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208787		k1r1t0	Bridges (APIO19_bridges)	C++20	59 / 100	3086 ms	14036 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int S = 500;
const int N = 110000;

int n, m, q, p[N], s[N], res[N];
vector<array<int, 3>> edge;
set<array<int, 4>> sorted;
bool bad[N], used[N], vrt[N];
vector<int> gr[N];

int dfs(int v) {
	if (vrt[v]) return 0;
	vrt[v] = true;
	int ans = s[v];
	for (int u : gr[v])
		ans += dfs(u);
	return ans;
}

void init() {
	for (int i = 1; i <= n; i++) {
		p[i] = i;
		s[i] = 1;
	}
}

int getp(int x) {
	return p[x] == x ? x : p[x] = getp(p[x]);
}

void unite(int a, int b) {
	a = getp(a);
	b = getp(b);
	if (a == b) return;
	if (s[a] < s[b])
		swap(a, b);
	s[a] += s[b];
	p[b] = a;
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, d; cin >> u >> v >> d;
		edge.push_back({u, v, d});
		sorted.insert({d, u, v, i - 1});
	}
	cin >> q;
	vector<array<int, 3>> qq;
	for (int i = 1; i <= q; i++) {
		int a, b, c; cin >> a >> b >> c; if (a == 1) b--;
		qq.push_back({a, b, c});
		if (i == q || (int) qq.size() == S) {
			for (int i = 0; i < m; i++)
				bad[i] = false;
			for (auto [a, b, c] : qq)
				if (a == 1) bad[b] = true;
			vector<array<int, 3>> good;
			vector<int> tbad;
			for (auto [a, b, c, d] : sorted)
				if (!bad[d]) good.push_back({b, c, a});
				else tbad.push_back(d);
			reverse(begin(good), end(good));
			vector<array<int, 3>> gg;
			for (int i = 0; i < (int) qq.size(); i++)
				if (qq[i][0] == 2) gg.push_back({qq[i][2], qq[i][1], i});
			sort(begin(gg), end(gg));
			reverse(begin(gg), end(gg));
			init();
			int ptr = 0;
			for (auto [a, b, c] : gg) {
				while (ptr < (int) good.size() && good[ptr][2] >= a) {
					unite(good[ptr][0], good[ptr][1]);
					ptr++;
				}
				for (int i = c; i >= 0; i--) {
					if (qq[i][0] == 2 || used[qq[i][1]])
						continue;
					used[qq[i][1]] = true;
					if (qq[i][2] >= a) {
						int x = edge[qq[i][1]][0];
						int y = edge[qq[i][1]][1];
						x = getp(x);
						y = getp(y);
						if (x == y) continue;
						gr[x].push_back(y);
						gr[y].push_back(x);
					}
				}
				for (int k : tbad)
					if (!used[k] && edge[k][2] >= a) {
						used[k] = true;
						int x = edge[k][0];
						int y = edge[k][1];
						x = getp(x);
						y = getp(y);
						if (x == y) continue;
						gr[x].push_back(y);
						gr[y].push_back(x);
					}
				res[c] = dfs(getp(b));
				vrt[getp(b)] = false;
				for (int k : tbad) {
					if (!used[k]) continue;
					used[k] = false;
					int x = edge[k][0];
					int y = edge[k][1];
					x = getp(x);
					y = getp(y);
					if (x == y) continue;
					gr[x].clear();
					gr[y].clear();
					vrt[x] = vrt[y] = false;
				}
			}
			for (int i = 0; i < (int) qq.size(); i++)
				if (qq[i][0] == 2)
					cout << res[i] << '\n';
			for (auto [a, b, c] : qq)
				if (a == 1) {
					sorted.erase({edge[b][2], edge[b][0], edge[b][1], b});
					edge[b][2] = c;
					sorted.insert({edge[b][2], edge[b][0], edge[b][1], b});
				}
			qq.clear();
		}
	}
}

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