Submission #1152769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152769		xnqs	Bridges (APIO19_bridges)	C++20	100 / 100	2849 ms	342012 KiB

bridges

/*
 * The main idea is to view the updates as time segments, more exactly an update has a start time and end time.
 * We will solve the queries offline, sorting them in ascending order of weight. Depending on where in the timeline
 * that query happened, we will work in one of the sqrt(N) DSUs that includes that timeline. This way, using DSU with
 * rollback, we can solve each query in O(sqrt(N)*log(N)), because there are at most sqrt(N) updates in a sqrt block.
 * Also, apparently the nodes are very small, so *maybe* we can try using uint16_t's to save some memory?
 *
 * Total time complexity: O(N*sqrt(N)*log(N))
 * Total space complexity: O(N*sqrt(N))
*/

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>
#include <numeric>
#include <unordered_map>
#include <cstdint>

const int BLK_SIZE = 727;

class DSURollback {
private:
	struct DSUState {
		uint16_t a, old_sz, b, old_t;
		DSUState():
			a(0), old_sz(0), b(0), old_t(0) {}
		DSUState(int a, int old_sz, int b, int old_t):
			a(a), old_sz(old_sz), b(b), old_t(old_t) {}
	};

	std::vector<uint16_t> t;
	std::vector<uint16_t> sz;
	std::vector<DSUState> stk;
public:
	DSURollback(int n = 0) {
		t.assign(n,0); std::iota(t.begin(),t.end(),0);
		sz.assign(n,1);
		stk.clear();
	}

	int Find(int k) {
		if (t[k]!=k) return Find(t[k]);
		return t[k];
	}
	
	int GetSize(int k) {
		return sz[Find(k)];
	}

	int Unite(int a, int b) {
		int ra = Find(a);
		int rb = Find(b);

		if (ra==rb) {
			return 0;
		}

		if (sz[ra]<sz[rb]) {
			std::swap(ra,rb);
		}
		
		stk.emplace_back(ra,sz[ra],rb,t[rb]);
		sz[ra] += sz[rb];
		t[rb] = t[ra];
		return 1;
	}

	int Undo() {
		if (stk.empty()) {
			return 0;
		}

		auto [a, old_sz, b, old_t] = stk.back();
		stk.pop_back();

		sz[a] = old_sz;
		t[b] = old_t;
		return 1;
	}
};

struct Edge {
	uint16_t a, b;
	int c;
	Edge():
		a(0), b(0), c(0) {}
	Edge(int a, int b, int c):
		a(a), b(b), c(c) {}
};

struct Query {
	int node, time, weight, idx;
	Query():
		node(0), time(0), weight(0), idx(0) {}
	Query(int node, int time, int weight, int idx):
		node(node), time(time), weight(weight), idx(idx) {}
};

int gs, edg, q;
std::vector<Edge> edges;
std::vector<Query> queries;

DSURollback decomp_dsu[BLK_SIZE];
std::vector<Edge> decomp_edges_no_upd[BLK_SIZE];
std::vector<std::tuple<int,int,int>> decomp_edges_upd[BLK_SIZE]; // get<0> = edge index
																 // get<1> = cost at that time
																 // get<2> = time
int ans[100005];

void add_event(int eidx, int l, int r) {
	int l_blk = l/BLK_SIZE;
	int r_blk = r/BLK_SIZE;

	if (l_blk==r_blk) {
		decomp_edges_upd[l_blk].emplace_back(eidx, edges[eidx].c, l);
		return;
	}
	if (l_blk+1==r_blk) {
		decomp_edges_upd[l_blk].emplace_back(eidx, edges[eidx].c, l);
		decomp_edges_upd[r_blk].emplace_back(eidx, edges[eidx].c, l);
		return;
	}

	if (l%BLK_SIZE==0) {
		decomp_edges_no_upd[l_blk].emplace_back(edges[eidx]);
	}
	else {
		decomp_edges_upd[l_blk].emplace_back(eidx, edges[eidx].c, l);
	}

	for (int i = l_blk+1; i <= r_blk-1; i++) {
		decomp_edges_no_upd[i].emplace_back(edges[eidx]);
	}

	if (r%BLK_SIZE==BLK_SIZE-1) {
		decomp_edges_no_upd[r_blk].emplace_back(edges[eidx]);
	}
	else {
		decomp_edges_upd[r_blk].emplace_back(eidx, edges[eidx].c, l);
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> gs >> edg;
	int timer = 0;
	std::vector<int> time_left(edg,0);
	for (int i = 0, a, b, c; i < edg; i++) {
		std::cin >> a >> b >> c;
		edges.emplace_back(a,b,c);
		time_left[i] = timer;
	}

	std::cin >> q;
	int query_cnt = 0;
	for (int i = 0; i < q; i++) {
		++timer;
		int op;
		std::cin >> op;

		if (op==1) {
			int eidx, val;
			std::cin >> eidx >> val;
			--eidx;

			add_event(eidx, time_left[eidx], timer-1);
			edges[eidx].c = val;
			time_left[eidx] = timer;
		}
		else {
			int node, max_w;
			std::cin >> node >> max_w;
			queries.emplace_back(node, timer, max_w, query_cnt++);
		}
	}

	for (int i = 0; i < edg; i++) {
		add_event(i, time_left[i], timer);
	}

	std::sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
		return a.weight > b.weight;
	});
	for (int i = 0; i < BLK_SIZE; i++) {
		decomp_dsu[i] = DSURollback(gs+5);
		std::sort(decomp_edges_no_upd[i].begin(), decomp_edges_no_upd[i].end(), [](const Edge& a, const Edge& b) {
			return a.c > b.c;
		});
		std::sort(decomp_edges_upd[i].begin(), decomp_edges_upd[i].end(), [](const std::tuple<int,int,int>& a, const std::tuple<int,int,int>& b) {
			return std::get<2>(a) < std::get<2>(b);
		});
	}

	int scanline[BLK_SIZE] = {0};
	std::vector<int> freq(100005,0);
	for (const auto& [node, time, weight, idx] : queries) {
		int blk = time / BLK_SIZE;
		while (scanline[blk] < decomp_edges_no_upd[blk].size() && decomp_edges_no_upd[blk][scanline[blk]].c >= weight) {
			decomp_dsu[blk].Unite(decomp_edges_no_upd[blk][scanline[blk]].a, decomp_edges_no_upd[blk][scanline[blk]].b);
			++scanline[blk];
		}

		int undos = 0;
		std::vector<int> stk;
		int pos = std::lower_bound(decomp_edges_upd[blk].begin(), decomp_edges_upd[blk].end(), std::tuple<int,int,int>(-1,-1,time)) - decomp_edges_upd[blk].begin();
		for (int i = decomp_edges_upd[blk].size()-1; i >= 0; i--) {
			auto [eidx, c, t] = decomp_edges_upd[blk][i];
			if (t > time) {
				continue;
			}

			if (!freq[eidx]) {
				if (c >= weight) {
					undos += decomp_dsu[blk].Unite(edges[eidx].a, edges[eidx].b);
				}
				freq[eidx] = 1;
				stk.emplace_back(eidx);
			}
		}

		ans[idx] = decomp_dsu[blk].GetSize(node);

		while (undos--) {
			decomp_dsu[blk].Undo();
		}
		while (!stk.empty()) {
			int k = stk.back();
			stk.pop_back();
			freq[k] = 0;
		}
	}

	for (int i = 0; i < query_cnt; i++) {
		std::cout << ans[i] << "\n";
	}
}

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