Submission #548601

#	Time	Username	Problem	Language	Result	Execution time	Memory
548601		GioChkhaidze	Bridges (APIO19_bridges)	C++14	44 / 100	3062 ms	5840 KiB

bridges

#include <bits/stdc++.h>

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

using namespace std;

const int N = 1e5 + 5;

bool used[N], T;
int n, m, q, ms;
int ans[N], p[N], sz[N], lc[N], cl[N];
int a[N], b[N], c[N], t[N], x[N], y[N];
vector < pair < int , pair < int , int > > > rec;

int P(int x) {
	if (x == p[x]) return x;
	if (T) rec.pb({x, {sz[x], p[x]}});
	return p[x] = P(p[x]);	
}

void uni(int a, int b) {
	a = P(a), b = P(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	if (T) rec.pb({a, {sz[a], p[a]}});
	if (T) rec.pb({b, {sz[b], p[b]}});
	sz[a] += sz[b];
	p[b] = a;
	return ;
}

void roll_back() {
	while (rec.size()) {
		int x = rec.back().f;
		sz[x] = rec.back().s.f;
		p[x] = rec.back().s.s;
		rec.pop_back();
	}
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> a[i] >> b[i] >> c[i];
		lc[i] = c[i];
	}
	
	cin >> q;
	ms = 1000;
	for (int i = 1; i <= q; ++i) {
		cin >> t[i] >> x[i] >> y[i];
	}

	vector < pair < pair < int , int > , int > > s;
	for (int i = 1; i <= q; i += ms) {
		vector < int > rc;
		int rm = min(i + ms - 1, q);
		for (int j = i; j <= rm; ++j) {
			if (t[j] == 1) {
				if (!used[x[j]]) rc.pb(x[j]);
				used[x[j]] = true;
			}
				else
			if (t[j] == 2) {
				s.pb({{y[j], 0}, j});	
			}
		}
		
		for (int j = 1; j < i; ++j) {
			if (t[j] == 2) continue;
			lc[x[j]] = y[j]; 
		}
		
		for (int j = 1; j <= m; ++j) {
			if (used[j]) { cl[j] = lc[j]; continue; }
			s.pb({{lc[j], 1}, j});
		}
		
		sort(s.begin(), s.end());
		for (int j = 1; j <= n; ++j) {
			p[j] = j, sz[j] = 1; 
		}
		
		for (int j = s.size() - 1; j >= 0; --j) {
			int tp = s[j].f.s;
			int cst = s[j].f.f;
			int id = s[j].s;

			if (tp) {
				uni(a[id], b[id]);
			}
				else {
				T = true;	
				for (int k = i; k <= id; ++k) {
					if (t[k] == 1) lc[x[k]] = y[k];
				}
				
				for (int k = 0; k < rc.size(); ++k) {
					int idx = rc[k];
					if (cst <= lc[idx]) {
						uni(a[idx], b[idx]);
					}
					lc[idx] = cl[idx];
				}
				
				ans[id] = sz[P(x[id])];
				roll_back();
				T = false;
			}
		}

		for (int j = i; j <= rm; ++j) {
			if (t[j] == 1) used[x[j]] = false;
		}
		s.clear();
	}
	
	for (int i = 1; i <= q; ++i) {
		if (t[i] == 2) cout << ans[i] << "\n";
	}
}

Compilation message (stderr)

bridges.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main () {
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int k = 0; k < rc.size(); ++k) {
      |                     ~~^~~~~~~~~~~

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