Submission #882992

#	Time	Username	Problem	Language	Result	Execution time	Memory
882992		serifefedartar	Bridges (APIO19_bridges)	C++17	14 / 100	605 ms	12224 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 1e5 + 10000;

const int SQRT = 1000;
struct Edge {
	int from, to, w, id;
	Edge() { }
	Edge(int _from, int _to, int _w, int _id) : from(_from), to(_to), w(_w), id(_id) { }
};

struct Query {
	int type, node, w, id;
	Query() { }
	Query(int _type, int _node, int _w, int _id) : type(_type), node(_node), w(_w), id(_id) { }
}; 

Edge edges[MAXN];
vector<Edge> srt;
Query queries[MAXN];
stack<pair<int,int>> st;
int par[MAXN], sz[MAXN], ans[MAXN], taken[MAXN], vis[MAXN], cnt2[MAXN];
int find(int node) {
	if (node == par[node])
		return node;
	return find(par[node]);
}

int cnt = 0;
void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return ;
	if (sz[b] > sz[a])
		swap(a, b);
	st.push({b, sz[b]});
	cnt++;
	sz[a] += sz[b];
	par[b] = a;
}

void rollback(int k) {
	while(st.size() && k--) {
		int nd = st.top().f;
		int siz = st.top().s;
		int pr = find(nd);
		st.pop();
		sz[nd] = siz;
		sz[pr] -= sz[nd]; 
		par[nd] = nd;
	}
}

void reset() {
	st = stack<pair<int,int>>();
	for (int i = 0; i < MAXN; i++)
		par[i] = i, sz[i] = 1;
}

int main() {
	int n, m, q;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> edges[i].from >> edges[i].to >> edges[i].w;
		edges[i].id = i;
		srt.push_back(Edge(edges[i].from, edges[i].to, edges[i].w, edges[i].id));
	}
	sort(srt.begin(), srt.end(), [&](Edge A, Edge B) {
		return A.w > B.w;
	});

	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> queries[i].type >> queries[i].node >> queries[i].w;
		if (queries[i].type == 1)
			queries[i].node--;
		queries[i].id = i;
	}

	for (int firstQ = 0; firstQ < q; firstQ += SQRT) {
		int lastQ = min(firstQ + SQRT, q - 1);

		vector<Query> update, ask;
		for (int i = firstQ; i <= lastQ; i++) {
			if (queries[i].type == 1) {
				update.push_back(queries[i]);
				taken[queries[i].node]++;
			} else
				ask.push_back(queries[i]);
		}
		reverse(update.begin(), update.end());
		sort(ask.begin(), ask.end(), [&](Query A, Query B) {
			return A.w < B.w;
		});
		reset();

		for (auto u : srt) {
			if (taken[u.id])
				continue;
			vector<int> v;
			while (ask.size() && ask.back().w > u.w) {
				cnt = 0;
				v = vector<int>();
				for (auto u : update) {
					if (vis[u.node] || u.id > ask.back().id) {
						cnt2[u.node]++;
						v.push_back(u.node);
						if (cnt2[u.node] == taken[u.node] && edges[u.node].w >= ask.back().w)
							unite(edges[u.node].from, edges[u.node].to);
						continue;
					}
					vis[u.node] = true;
					if (u.w >= ask.back().w)
						unite(edges[u.node].from, edges[u.node].to);
				}
				ans[ask.back().id] = sz[find(ask.back().node)];
			
				rollback(cnt);
				for (auto u : update)
					vis[u.node] = false;
				for (auto u : v)
					cnt2[u] = 0;
				ask.pop_back();
			}
			unite(u.from, u.to);
		}

		while (ask.size()) {
			cnt = 0;
			vector<int> v;
			for (auto u : update) {
				if (vis[u.node] || u.id > ask.back().id) {
					v.push_back(u.node);
					cnt2[u.node]++;
					if (cnt2[u.node] == taken[u.node] && edges[u.node].w >= ask.back().w)
						unite(edges[u.node].from, edges[u.node].to);
					continue;
				}
				vis[u.node] = true;
				if (u.w >= ask.back().w)
					unite(edges[u.node].from, edges[u.node].to);
			}
			ans[ask.back().id] = sz[find(ask.back().node)];

			rollback(cnt);
			for (auto u : update)
				vis[u.node] = false;
			for (auto u : v)
					cnt2[u] = 0;
			ask.pop_back();
		}

		rollback(1e7);
		for (auto u : update)
			taken[u.node]--;
	}

	for (int i = 0; i < q; i++) {
		if (queries[i].type == 2)
			cout << ans[i] << "\n";
	}
}

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