Submission #906759

#	Time	Username	Problem	Language	Result	Execution time	Memory
906759		beaboss	Bridges (APIO19_bridges)	C++14	100 / 100	2102 ms	12172 KiB

bridges

// Source: https://oj.uz/problem/view/APIO19_bridges
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int Q = 1e5 + 10;
const int N = 5e4 + 10;
const int B = 1e3;

int t[Q], x[Q], y[Q];
int a[Q], b[Q], w[Q];

stack<vi> ops;
vi p(N, -1);
int res[Q];

int get(int cur) {
	return p[cur] < 0 ? cur : get(p[cur]);
}

void unite(int x, int y) {
	x = get(x);
	y = get(y);

	if (x == y) return;

	if (-p[x] < -p[y]) swap(x, y);

	ops.push({y, p[y], x});


	p[x] += p[y];
	p[y] = x;

	// cout << ' ' << x << p[x] << endl;
}

void rollback() {
	while (!ops.empty()) {
		vi cur = ops.top();
		ops.pop();
		p[cur[0]] = cur[1];
		p[cur[2]] -= cur[1];
	}
}




int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;

	FOR(i, 1, m + 1) {
		cin >> a[i] >> b[i] >> w[i];
	}

	int q;
	cin >> q;
	FOR(i, 1, q + 1) cin >> t[i] >> x[i] >> y[i];


	for (int l = 1; l <= q; l += B+1) {

		FOR(i, 1, n + 1) p[i]=-1;
		// cout << l << endl;
		int r = min(l + B, q);

		vector<bool> changed(m + 1, false);
		vpii unchanged;
		vector<vi> add(r - l + 1);
		vpii query;

		for (int i = l; i <= r; i++) {
			if (t[i] == 1) {
				w[x[i]] = y[i]; // set the new weight
				changed[x[i]]=true;
			} else {
				for (int j = l; j <= r; j++) {
					if (t[j] == 1 && w[x[j]] >= y[i]) {
						// cout << ' ' << i << x[j] << endl;
						add[i - l].pb(x[j]); // add this new update if we can cross this bridge
					}
				}
				query.pb({y[i], i});
			}
		}

		FOR(i, 1, m + 1) if (!changed[i]) {
			unchanged.pb({w[i], i});
		}

		// cout << unchanged.size() << endl;

		sort(unchanged.rbegin(), unchanged.rend());
		sort(query.rbegin(), query.rend());

		int un_ind = 0;

		
		for (auto ask: query) {
			while (un_ind != unchanged.size() && unchanged[un_ind].f >= y[ask.s]) {
				// cout << ask.s << unchanged[un_ind].s << endl;
				unite(a[unchanged[un_ind].s], b[unchanged[un_ind].s]);
				un_ind++;
			}

			while (!ops.empty()) ops.pop();

			for (auto merge: add[ask.s - l]) {
				// cout << ask.s << merge << endl;
				unite(a[merge], b[merge]);
			}
			// cout << ask.s << -p[get(x[ask.s])] << endl;
			res[ask.s] = -p[get(x[ask.s])];

			rollback();
		}




		
	}

	FOR(i, 1, q + 1) {
		if (t[i] == 2) {
			// cout << i << endl;
			cout << res[i] << endl;
		}
	}


}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |    while (un_ind != unchanged.size() && unchanged[un_ind].f >= y[ask.s]) {
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~

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