Submission #361909

#	Time	Username	Problem	Language	Result	Execution time	Memory
361909		hoaphat1	Bridges (APIO19_bridges)	C++17	0 / 100	3083 ms	9144 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

struct dsu {
	vector<int> p;
	vector<pair<int,int>> event;
	dsu(int n) {
		p.resize(n, -1);
		event.resize(2 * n);
	}
	int get(int x) {
		return p[x] < 0 ? x : get(p[x]);
	}
	int id = 0;
	bool unite(int x, int y, bool need = false) {
		x = get(x);y = get(y);
		if (x != y) {
			if (p[x] > p[y]) swap(x, y);
			if (need) {
				event[id++] = {x, p[x]};
				event[id++] = {y, p[y]};
			}
			p[x] += p[y];
			p[y] = x;
			return true;
		}
		return false;
	}
	void recall() {
		while (id) {
			id--;
			p[event[id].first] = event[id].second;
		}
	}
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  cin >> n >> m;
  #define getp(x, a) get<a>(x)
  vector<tuple<int, int, int>> edges;
  for (int i = 0; i < m; i++) {
  	int u, v, w;
  	cin >> u >> v >> w;
  	--u; --v;
  	edges.emplace_back(u, v, w);
	}
	int q;
	cin >> q;
	vector<tuple<int, int, int>> Query;
	for (int i = 0; i < q; i++) {
		int t, v, w;
		cin >> t >> v >> w;
		--v;
		Query.emplace_back(t, v, w);
	}
	const int Q = sqrt(q);
	vector<bool> kt(m);
	vector<int> ans(q);
	vector<int> last(m, -1);
	vector<bool> used(m);
	for (int i = 0; i < q; i += Q) {
		int l = i, r = min(q, i + Q);
		for (int i = 0; i < m; i++) kt[i] = false;
		for (int i = l; i < r; i++) {
			if (getp(Query[i], 0) == 1) kt[getp(Query[i], 1)] = true;
		}
		vector<int> idx;
		for (int i = 0; i < m; i++) if (!kt[i]) idx.push_back(i);
		sort(idx.begin(), idx.end(), [&](int i, int j) {
			return getp(edges[i], 2) > getp(edges[j], 2);
		});
		vector<int> udp;
		vector<int> ask;
		vector<int> inq;
		for (int i = l; i < r; i++) {
			if (getp(Query[i], 0) == 1) {
				udp.push_back(i);
				if (!used[getp(Query[i], 1)]) {
					used[getp(Query[i], 1)] = true;
					inq.push_back(getp(Query[i], 1));
				}
			}
			else ask.push_back(i);
		}
		sort(ask.begin(), ask.end(), [&](int i, int j) {
			return getp(Query[i], 2) > getp(Query[j], 2);
		});
		int pos = 0;
		dsu d(n);
		for (auto& id : ask) {

			while (pos < (int) idx.size() && getp(edges[idx[pos]], 2) >= getp(Query[id], 2)) {
				d.unite(getp(edges[idx[pos]], 0), getp(edges[idx[pos]], 1));
				pos++;
			}
			for (auto& x : udp) {
				if (x > id) break;
				last[getp(Query[x], 1)] = x;
			}
			for (auto& x : inq) {
				int val;
				if (last[x] == -1) val = getp(edges[x], 2);
				else val = getp(Query[last[x]], 2);
				if (val >= getp(Query[id], 2)) {
					const auto& e = edges[x];
					d.unite(getp(e, 0), getp(e, 1), 1);
				}
			}
			ans[id] = -d.p[d.get(getp(Query[id], 1))];
			d.recall();
			for (auto&x : udp) {
				if (x > id) break;
				last[getp(Query[x], 1)] = -1;
			}
		}
		
		for (int i = l; i < r; i++) {
			if (getp(Query[i], 0) == 1) {
				used[getp(Query[i], 0)] = false;
				getp(edges[getp(Query[i], 1)], 2) = getp(Query[i], 2);
			}
		}
	}
	for (int i = 0; i < q; i++) if (getp(Query[i], 0) == 2) cout << ans[i] <<"\n";
}

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