Submission #966395

#	Time	Username	Problem	Language	Result	Execution time	Memory
966395		iliaaaaa	Bridges (APIO19_bridges)	C++17	100 / 100	1988 ms	13912 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define All(x) (x).begin(),(x).end()
#define len(x) (int)(x).size()
#define pb push_back

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

const int N = 1e5 + 7, SQ = 1000;
int n, m, q, ans[N], idx[N], par[N], T[N], X[N], Y[N];
vector<pair<pii, int>> record;
bool change[N], frst[N];
vector<int> qu[N];
edge ed[N];

int get_par(int u) {
	return par[u] < 0? u: get_par(par[u]);
}

void merge(int u, int v) {
	u = get_par(u), v = get_par(v);
	if (u == v) {
		record.pb({{-1, -1}, 0});
		return;
	}
	if (par[u] < par[v])
		swap(u, v);
	record.pb({{u, v}, par[u]});
	par[v] += par[u];
	par[u] = v;
}

void undo() {
	pair<pii, int> r = record.back();
	record.pop_back();
	if (r.F.F == -1)
		return;
	int u = r.F.F, v = r.F.S;
	par[u] = r.S;
	par[v] -= par[u];
}

int32_t main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> ed[i].u >> ed[i].v >> ed[i].w;
		ed[i].u--, ed[i].v--;
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> T[i] >> X[i] >> Y[i];
		X[i]--;
	}
	vector<int> vec;
	for (int i = 0; i < q; i += SQ) {
		vec.clear();
		fill(change, change + m, 0);
		iota(idx, idx + m, 0);
		sort(idx, idx + m, [] (int i, int j) {
				return ed[i].w < ed[j].w;
				});
		for (int j = i; j < min(q, i + SQ); j++)
			if (T[j] == 1)
				change[X[j]] = true;
		for (int i = 0; i < m; i++)
			vec.pb(ed[idx[i]].w);
		for (int i = 0; i <= m; i++)
			qu[i].clear();
		for (int j = i; j < min(q, i + SQ); j++)
			if (T[j] == 2) 
				qu[lower_bound(All(vec), Y[j]) - vec.begin()].pb(j);
		fill(par, par + n, -1);
		record.clear();
		for (int j = m; j >= 0; j--) {
			if (j < m && !change[idx[j]]) {
				int u = ed[idx[j]].u, v = ed[idx[j]].v;
				merge(u, v);
			}
			for (int idx: qu[j]) {
				int cnt = 0;
				for (int k = idx; k >= i; k--)
					if (T[k] == 1 && !frst[X[k]]) {
						frst[X[k]] = true;
						if (Y[k] >= Y[idx]) {
							int u = ed[X[k]].u, v = ed[X[k]].v;
							merge(u, v);
							cnt++;
						}
					}
				for (int k = i; k < min(q, i + SQ); k++)
					if (T[k] == 1 && !frst[X[k]]) {
						if (ed[X[k]].w >= Y[idx]) {
							int u = ed[X[k]].u, v = ed[X[k]].v;
							merge(u, v);
							cnt++;
						}
					}
				ans[idx] = abs(par[get_par(X[idx])]);
				while (cnt--)
					undo();
				for (int j = i; j < min(q, i + SQ); j++)
					frst[X[j]] = false;
			}
		}
		for (int j = i; j < min(q, i + SQ); j++)
			if (T[j] == 1)
				ed[X[j]].w = Y[j];
	}
	for (int i = 0; i < q; i++)
		if (T[i] == 2)
			cout << ans[i] << '\n';
	return 0;
}

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