Submission #363969

#	Time	Username	Problem	Language	Result	Execution time	Memory
363969		penguinhacker	Bridges (APIO19_bridges)	C++14	100 / 100	2934 ms	11052 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 100000;
const int B = 750;
int n, m, q, ans[mxN];
int par[mxN], sz[mxN];

ar<int, 3> e[mxN];
ar<int, 3> qry[mxN];

vector<int> rb;

void reset() {
	rb.clear();
	fill(sz, sz + n, 1);
	iota(par, par + n, 0);
}

int find(int i) {
	while(i != par[i]) i = par[i];
	return i;
}

void merge(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	rb.push_back(b);
	sz[a] += sz[b];
	par[b] = a;
}

void rollback(int k) {
	while(rb.size() > k) {
		int b = rb.back();
		rb.pop_back();
		sz[par[b]] -= sz[b];
		par[b] = b;
	}
}

vector<int> to_join[B];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) cin >> e[i][0] >> e[i][1] >> e[i][2], --e[i][0], --e[i][1];
	cin >> q;
	for (int i = 0; i < q; ++i) cin >> qry[i][0] >> qry[i][1] >> qry[i][2], --qry[i][1];

	for (int l = 0; l < q; l += B) {
		reset();
		int r = min(q, l + B);
		vector<bool> changed(m);
		for (int i = l; i < r; ++i) if (qry[i][0] == 1) changed[qry[i][1]] = 1;

		vector<int> upd, unchanged, ask;
		for (int i = 0; i < m; ++i) {
			if (changed[i]) upd.push_back(i);
			if (!changed[i]) unchanged.push_back(i);
		}
		for (int i = l; i < r; ++i) {
			if (qry[i][0] == 1) e[qry[i][1]][2] = qry[i][2];
			else {
				to_join[i - l].clear();
				for (int ind : upd) if (e[ind][2] >= qry[i][2]) to_join[i - l].push_back(ind);
				ask.push_back(i);
			}
		}
		sort(unchanged.begin(), unchanged.end(), [&](int a, int b) {return e[a][2] < e[b][2];});
		sort(ask.begin(), ask.end(), [&](int a, int b) {return qry[a][2] > qry[b][2];});
		for (int i : ask) {
			while(!unchanged.empty()) {
				int x = unchanged.back();
				if (e[x][2] < qry[i][2]) break;
				merge(e[x][0], e[x][1]);
				unchanged.pop_back();
			}
			int prv_sz = rb.size();
			for (int x : to_join[i - l]) merge(e[x][0], e[x][1]);
			ans[i] = sz[find(qry[i][1])];
			rollback(prv_sz);
		}
	}
	for (int i = 0; i < q; ++i) if (qry[i][0] == 2) cout << ans[i] << "\n";
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:38:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |  while(rb.size() > k) {
      |        ~~~~~~~~~~^~~

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