Submission #545500

#	Time	Username	Problem	Language	Result	Execution time	Memory
545500		Mazaalai	Bridges (APIO19_bridges)	C++17	100 / 100	2013 ms	40732 KiB

bridges

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII = pair <int, int>;
const int N = 5e4+5;
const int M = 1e5+5;
const int BLOCK = 1000;
int n, m, k, q;
bool changed[M];
int u[M], v[M], w[M];
vector <int> join[BLOCK];
vector <int> updates, curQueries, unchanged;
// queries
int ans[M];
PII queries[M];
bool type[M], QUERY = 1;
// DSU
vector <int> stk;
int par[N], sz[N];
int find(int a) {
	while (par[a] != a) a = par[a];
	return a;
}
void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	sz[a] += sz[b];
	par[b] = a;
	stk.pb(b);
}
void rewind(int tar) {
	while(stk.size() > tar) {
		int cur = stk.back(); stk.pop_back();
		sz[par[cur]] -= sz[cur];
		par[cur] = cur;
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("0.in", "r", stdin);
	// freopen("0.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) 
		cin >> u[i] >> v[i] >> w[i];
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int t; cin >> t >> queries[i].ff >> queries[i].ss;
		type[i] = t-1;
	}
	for (int l = 1; l <= q; l+=BLOCK) {
		int r = min(l+BLOCK-1, q);
		// reset
		updates.clear();
		unchanged.clear();
		curQueries.clear();
		fill(sz+1, sz+1+n, 1);
		iota(par+1, par+1+n, 1);
		fill(changed+1, changed+m+1, 0);
		// solution
		for (int i = l; i <= r; i++) {
			if (type[i] == QUERY) {
				curQueries.pb(i);
			} else { // type[i] == UPDATE
				changed[queries[i].ff] = 1;
				updates.pb(i);
			}
		}
		for (int i = 1; i <= m; i++) 
			if (!changed[i]) unchanged.pb(i);
		
		for (int i = l; i <= r; i++) {
			if (type[i] == QUERY) {
				join[i-l].clear();
				for (auto el : updates)
					if (w[queries[el].ff] >= queries[i].ss) join[i-l].pb(queries[el].ff);
			} else { // type[i] == UPDATE
				w[queries[i].ff] = queries[i].ss;
			}
		}
		sort(ALL(curQueries), [&](int a, int b) { return queries[a].ss > queries[b].ss; });
		sort(ALL(unchanged), [&](int a, int b) { return w[a] > w[b]; });
		int pt = 0;
		for (auto query : curQueries) {
			while(pt < unchanged.size() && w[unchanged[pt]] >= queries[query].ss) {
				int pos = unchanged[pt++];
				merge(u[pos], v[pos]);
			}
			int curSz = stk.size();
			for (auto el : join[query-l]) merge(u[el], v[el]);
			ans[query] = sz[find(queries[query].ff)];
			rewind(curSz);
		}
	}
	for (int i = 1; i <= q; i++) 
		if (type[i] == QUERY) cout << ans[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In function 'void rewind(int)':
bridges.cpp:37:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |  while(stk.size() > tar) {
      |        ~~~~~~~~~~~^~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:91:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    while(pt < unchanged.size() && w[unchanged[pt]] >= queries[query].ss) {
      |          ~~~^~~~~~~~~~~~~~~~~~

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