Submission #361912

#	Time	Username	Problem	Language	Result	Execution time	Memory
361912		hoaphat1	Bridges (APIO19_bridges)	C++17	0 / 100	3056 ms	12384 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((int) 1e6);
	}
	int get(int x, bool need = false) {
		if (p[x] < 0) return x;
		if (need) event[id++] = {x, p[x]};
		return p[x] = get(p[x], need);
	}
	int id = 0;
	bool unite(int x, int y, bool need = false) {
		x = get(x, need);y = get(y, need);
		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 = 365;
	/// q/Q * (mlogm + Q + m + Q * Q)
	vector<int> ans(q);
	vector<int> last(m, -1);
	vector<bool> used(m);
	dsu d(n);
	vector<int> idx;
	vector<int> udp;
	vector<int> ask;
	vector<int> inq;
	for (int i = 0; i < q; i += Q) {
		int l = i, r = min(q, i + Q);
		for (int i = 0; i < n; i++) d.p[i] = -1;
		idx.clear();
		udp.clear();
		ask.clear();
		inq.clear();
		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);
		}
		for (int i = 0; i < m; i++) if (!used[i]) idx.push_back(i);
		sort(idx.begin(), idx.end(), [&](int i, int j) {
			return getp(edges[i], 2) > getp(edges[j], 2);
		});
		sort(ask.begin(), ask.end(), [&](int i, int j) {
			return getp(Query[i], 2) > getp(Query[j], 2);
		});
		int pos = 0;
		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], 1)] = 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