Submission #383084

#	Time	Username	Problem	Language	Result	Execution time	Memory
383084		Kalashnikov	Bridges (APIO19_bridges)	C++17	100 / 100	2718 ms	9776 KiB

bridges

#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 1e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;

int K = 800;

int u[N] , v[N] , d[N] , t[N] , a[N] , b[N] , used[N] , p[N] , sz[N] , ans[N];

vector<pair<int*,int>> rollback;

int get(int v) {
	if(p[v] == v) return v;
	return get(p[v]);
}

void merge(int a, int b , int keep = 0) {
	a = get(a);
	b = get(b);
	if(a == b) return;
	if(sz[a] < sz[b]) swap(a , b);
	if(keep) {
		rollback.push_back({&sz[a] , sz[a]});
		rollback.push_back({&p[b] , p[b]});
	}
	sz[a] += sz[b];
	p[b] = a;
}

void solve() {
	int n , m , q;
	cin >> n >> m;
	for(int i = 1; i <= m; i ++) {
		cin >> u[i] >> v[i] >> d[i];
	}
	cin >> q;
	int last = 0;
	for(int i = 0; i <= q; i ++) {
		if((i % K == 0 && i != 0) || i == q) {
			vector<pair<int,int>> cons;
			vector<int> necons;
			for(int j = 1; j <= m; j ++) {
				if(used[j] == 0) {
					cons.push_back({d[j] , j});
				}
				else {
					necons.push_back(j);
				}
				used[j] = 0;
			}
			sort(all(cons));
			
			for(int j = 1; j <= n; j ++) {
				p[j] = j;
				sz[j] = 1;
			}
			vector<pair<int,int>> ques;
			vector<int> changes;
			for(int j = last; j < i; j ++) {
				if(t[j] == 2) {
					ques.push_back({b[j] , j});
				}
				else {
					changes.push_back(j);
				}
			}
			sort(all(ques));
			reverse(all(ques));
			
			for(auto x: ques) {
		//		cout << x.F << ' ' << x.S << '\n';
				while(cons.size() && cons.back().F >= x.F) {
					merge(u[cons.back().S] , v[cons.back().S]);
					cons.pop_back();
				}
				for(auto to: changes) {
					if(to > x.S) break;
					//cout << "   ";
				//	cout << a[to] << ' ' << b[to] << '\n';
					rollback.push_back({&d[a[to]] , d[a[to]]});
					d[a[to]] = b[to];
				}
				for(auto to: necons) {
					if(d[to] >= x.F) {
						merge(u[to] , v[to] , 1);
					}
				}
				ans[x.S] = sz[get(a[x.S])];
				while(rollback.size()) {
					*rollback.back().F = rollback.back().S;
					rollback.pop_back();
				}
			}
			for(auto to: changes) {
				d[a[to]] = b[to];
			}
			last = i;
		}
		if(i == q) break;
		cin >> t[i] >> a[i] >> b[i];
		if(t[i] == 1) {
			used[a[i]] = 1;
		}
	}
	
	//cout << "BRIDGE\n";
	
	for(int i = 0; i < q; i ++) {
		if(t[i] == 2) {
			cout << ans[i] << '\n';
		}
	}
}
/*
*/
main() {
    ios;
    int tt = 1;
    //cin >> tt;
    while(tt --) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp:125:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  125 | main() {
      |      ^

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