Submission #676933

#	Time	Username	Problem	Language	Result	Execution time	Memory
676933		Sohsoh84	Bridges (APIO19_bridges)	C++17	100 / 100	2200 ms	12284 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const int MAXN = 1e5 + 10;
const int SQ = 400;

int U[MAXN], V[MAXN], W[MAXN], par[MAXN], n, m, q, TW[MAXN],
    QT[MAXN], QA[MAXN], QB[MAXN], QANS[MAXN], sz[MAXN];

list<int> adj[MAXN];
vector<int> vis_vec;
vector<pll> events;
bool edge_mark[MAXN], vis[MAXN];

int find(int v) {
	return par[v] == v ? v : par[v] = find(par[v]);
}

inline void unite(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	if (sz[u] < sz[v]) swap(u, v);

	par[v] = u;
	adj[u].splice(adj[u].end(), adj[v]);
	sz[u] += sz[v];
}

int dfs(int v, int lim) {
	vis[v] = true;
	vis_vec.push_back(v);
	int ans = sz[v];

	for (int ind : adj[v]) {
		int u = find(V[ind]) ^ find(U[ind]) ^ v;
		if (lim <= W[ind] && !vis[u])
			ans += dfs(u, lim);
	}

	return ans;
}

inline void solve(int l, int r) {
	for (int i = 1; i <= n; i++) {
		par[i] = i;
		sz[i] = 1;
		adj[i].clear();
	}

	for (int i = l; i < r; i++) {
		if (QT[i] == 1) {
			edge_mark[QA[i]] = true;
			adj[U[QA[i]]].push_back(QA[i]);
			adj[V[QA[i]]].push_back(QA[i]);
			TW[QA[i]] = W[QA[i]];
		}
	}

	for (auto [b, a] : events) {
		if (a > m && QT[a - m - 1] == 1) a = QA[a - m - 1];
		if (a <= m && (W[a] != b || edge_mark[a])) continue;
		if (a > m && (a - m - 1 < l || a - m - 1 >= r)) continue;	
		
		if (a <= m) unite(U[a], V[a]);
		else {
			a -= m + 1;
			
			for (int i = l; i < a; i++)
				if (QT[i] == 1)
					W[QA[i]] = QB[i];

			QANS[a] = dfs(find(QA[a]), b);	
			for (int e : vis_vec)
				vis[e] = false;
			vis_vec.clear();
		
			for (int i = l; i < a; i++)
				if (QT[i] == 1)
					W[QA[i]] = TW[QA[i]];
		}
	}

	for (int i = l; i < r; i++) {
		if (QT[i] == 1) {
			edge_mark[QA[i]] = false;
			W[QA[i]] = QB[i];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> U[i] >> V[i] >> W[i];
		events.push_back({W[i], i});
	}

	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> QT[i] >> QA[i] >> QB[i];
		events.push_back({QB[i], m + i + 1});
	}

	sort(all(events), [] (pll a, pll b) {
		if (a.X == b.X) return a.Y < b.Y;
		return a.X > b.X;
	});

	for (int i = 0; i < q; i += SQ) {
		vector<pair<int, pll>> vec;
		solve(i, min(i + SQ, q));	
	}

	for (int i = 0; i < q; i++)
		if (QT[i] == 2) 
			cout << QANS[i] << endl;
	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