Submission #263611

#	Time	Username	Problem	Language	Result	Execution time	Memory
263611		hanagasumi	Bridges (APIO19_bridges)	C++17	30 / 100	3082 ms	17532 KiB

bridges

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef long double ld;

struct edge {
	int v, u, w;
};

struct zap {
	int tp, id, w;
};


vector<int> p;
vector<int> sz;

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

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

void merge(int a, int b) {
	a = getp(a), b = getp(b);
	if(a == b) 
		return;
	if(sz[a] < sz[b]) 
		swap(a, b);
	p[b] = a;
	sz[a] += sz[b];
}

void merge(int a, int b, vector<pair<int, pair<int, int>>>& otk) {
	a = findp(a), b = findp(b);
	if(a == b)
		return;
	if(sz[a] < sz[b]) 
		swap(a, b);
	otk.pb({b, {p[b], sz[b]}});
	otk.pb({a, {p[a], sz[a]}});
	p[b] = a;
	sz[a] += sz[b];
}

signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m, q;
	cin >> n >> m;
	vector<edge> e;
	vector<vector<int>> g(n);
	p = vector<int> (n);
	sz = vector<int> (n);
	vector<zap> z;
	int k = 400;
	int maxk;
	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		a--, b--;
		e.pb({a, b, w});
	}

	cin >> q;
	vector<int> ans(q, -1);
	maxk = (q - 1) / k;
	for (int qq = 0; qq < q; qq++) {
		int tp, id, w;
		cin >> tp >> id >> w;
		id--;
		z.pb({tp, id, w});
	}

	for (int i = 0; i <= maxk; i++) {
		int end = min(q, (i + 1) * k), beg = i * k;
		for (int i = 0; i < n; i++) 
			p[i] = i, sz[i] = 1;
		vector<bool> used(m, 1);
		vector<pair<int, pair<int, int>>> ask;
		vector<int> bad;

		for (int i = beg; i < end; i++) {
			if(z[i].tp == 2) {
				ask.pb({z[i].w, {0, i}});
				continue;
			}
			used[z[i].id] = 0;
		}
		for (int i = 0; i < m; i++) {
			if(!used[i]) {
				bad.pb(i);
				continue;
			}
			ask.pb({e[i].w, {1, i}});
		}
		// for (auto x : bad) 
		// 	cout << x << " ";
		// cout << endl;
		sort(all(ask)); 
		reverse(all(ask));
		
		for (int i = 0; i < len(ask); i++) {
			// cout << "SOB: " << ask[i].ft << " " << ask[i].sc.ft << " " << ask[i].sc.sc << endl;
			if(ask[i].sc.ft == 1) {
				merge(e[ask[i].sc.sc].v, e[ask[i].sc.sc].u);
				continue;
			}
			int num = ask[i].sc.sc;
			vector<pair<int, int>> eo;
			vector<pair<int, pair<int, int>>> po;
			for (int i = beg; i < num; i++) {
				if(z[i].tp == 2) 
					continue;
				eo.pb({z[i].id, e[z[i].id].w});
				e[z[i].id].w = z[i].w;
			}
			for (auto x : bad) {
				if(e[x].w < z[num].w) 
					continue;
				merge(e[x].u, e[x].v, po);
			}
			ans[num] = sz[findp(z[num].id)];
			reverse(all(po));
			reverse(all(eo));
			for (auto x : eo) {
				e[x.ft].w = x.sc;
			}
			for (auto x : po) {
				p[x.ft] = x.sc.ft;
				sz[x.ft] = x.sc.sc;
			}
		}
		for (int i = beg; i < end; i++) {
			if(z[i].tp == 2)
				continue;
			e[z[i].id].w = z[i].w;
		}
	}


	for (int i = 0; i < q; i++) {
		// cout << ans[i] << " ";
		if(ans[i] == -1) 
			continue;
		cout << ans[i] << '\n';
	}
}

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