Submission #548610

#	Time	Username	Problem	Language	Result	Execution time	Memory
548610		GioChkhaidze	Bridges (APIO19_bridges)	C++14	100 / 100	2557 ms	12248 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;
vector < pair < pair < int , int > , int > > s, e, e1, e2, e3;

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]; 
		e.pb({{c[i], 1}, i});
		lc[i] = cl[i] = c[i];
	}
	
	cin >> q;
	ms = 700;
	sort(e.begin(), e.end());
	for (int i = 1; i <= q; ++i) {
		cin >> t[i] >> x[i] >> y[i];
	}
	
	int id1, id2, id3, e1s, e2s, e3s;
	for (int i = 1; i <= q; i += ms) {
		e1.clear();
		e2.clear();
		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) {
				e1.pb({{y[j], 0}, j});	
			}
		}

		sort(e1.begin(), e1.end());
		for (int j = 0; j < e.size(); ++j) {
			if (used[e[j].s]) continue;
			e2.pb(e[j]);
		}

		s.clear();
		id1 = 0, e1s = e1.size();
		id2 = 0, e2s = e2.size();
		while (id1 < e1s || id2 < e2s) {
			if (id2 == e2s || (id1 < e1s && e1[id1] < e2[id2])){
				s.pb(e1[id1]), id1++;
			}
				else
			if (id1 == e1s || (id2 < e2s && e2[id2] < e1[id1])) {
				s.pb(e2[id2]), id2++;
			}
		}
		
		for (int j = 1; j < i; ++j) {  
			if (t[j] == 2) continue;
			lc[x[j]] = cl[x[j]] = y[j]; 
		}
		
		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;
			}
		}

		e3.clear();
		for (int j = rm; j >= i; --j) {
			if (t[j] == 1) {
				if (used[x[j]]) {
					e3.pb({{y[j], 1}, x[j]});
					lc[x[j]] = cl[x[j]] = y[j];
					used[x[j]] = false;
				}
			}
		}

		e.clear();
		id2 = 0, e2s = e2.size();
		id3 = 0, e3s = e3.size();
		sort(e3.begin(), e3.end());
		while (id3 < e3s || id2 < e2s) {
			if (id2 == e2s || (id3 < e3s && e3[id3] < e2[id2])) {
				e.pb(e3[id3++]);
			}
				else
			if (id3 == e3s || (id2 < e2s && e2[id2] < e3[id3])) {
				e.pb(e2[id2++]);
			}
		}
	}
	
	for (int i = 1; i <= q; ++i) {
		if (t[i] == 2) cout << ans[i] << "\n";
	}
}

Compilation message (stderr)

bridges.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main () {
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for (int j = 0; j < e.size(); ++j) {
      |                   ~~^~~~~~~~~~
bridges.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int k = 0; k < rc.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