Submission #1210866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210866		dubabuba	Bridges (APIO19_bridges)	C++17	100 / 100	1330 ms	13376 KiB

bridges

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

const int mxn = 1e5 + 100;
const int BLOCK_sz = 1500;

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

struct edge {
	int id, w, u, v;
	edge() : id(0), w(0), u(0), v(0) {}
	edge(int id, int u, int v, int w) : id(id), w(w), u(u), v(v) {}
	const friend bool operator < (const edge e1, const edge e2) {
		if(e1.w != e2.w) return e1.w > e2.w;
		return e1.id < e2.id;
	}
};

struct query {
	int id, u, w;
	query() : id(0), u(0), w(0) {}
	query(int id, int u, int w) : id(id), u(u), w(w) {}

	const friend bool operator < (const query q1, const query q2) {
		if(q1.w != q2.w) return q1.w > q2.w;
		return q1.id < q2.id;
	}
};

struct DSU {
	const int N = 5e4 + 10;
	int par[mxn];
	stack<pair<pii, pii>> hist;

	DSU() {
		memset(par, -1, sizeof par);
		while(hist.size())
			hist.pop();
	}

	void init() {
		memset(par, -1, sizeof par);
		while(hist.size())
			hist.pop();
	}

	int parent(int u) {
		while(par[u] > 0) u = par[u];
		return u;
	}

	void unite(int u, int v) {
		u = parent(u);
		v = parent(v);
		if(u == v) return;

		if(par[u] > par[v]) swap(u, v);
		hist.push(MP(MP(u, par[u]), MP(v, par[v])));
		par[u] += par[v];
		par[v] = u;
	}

	void roll_back(int sz) {
		while(hist.size() > sz) {
			int u, v, pu, pv;
			tie(u, pu) = hist.top().ff;
			tie(v, pv) = hist.top().ss;

			par[u] = pu;
			par[v] = pv;
			hist.pop();
		}
	}
};

int type[mxn], n, m, q;
vector<pii> query(mxn);
vector<pii> edges(mxn);
int weight[mxn], ans[mxn];
set<edge> SET;

int main() {
	#ifdef LOCAL
	auto TIME_st = chrono::steady_clock::now();
	#endif

	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		SET.insert(edge(i, u, v, w));
		weight[i] = w;
		edges[i] = MP(u, v);
	}

	cin >> q;
	for(int i = 0; i < q; i++) {
		cin >> type[i] >> query[i].ff >> query[i].ss;
	}

	function<void(int)> eraser = [&](int i) { SET.erase(edge(i, edges[i].ff, edges[i].ss, weight[i])); };
	// function<void(int, int)> connect = [&](int u, int v) { azaa.uni };
	for(int L = 0; L < q; L += BLOCK_sz) {
		int R = min(q, L + BLOCK_sz);

		// cout << "\nrange = ";
		// cout << L << " " << R << "\n";
		// cout << "SET was:\n";
		// for(auto t : SET) {
		// 	cout << t.id << ' ' << t.u << ' ' << t.v << " = " << t.w << " == " << weight[t.id] << endl;
		// }

		vector<int> upt, ask;
		for(int i = L; i < R; i++) {
			int x = query[i].ff;
			int w = query[i].ss;
			if(type[i] == 2) {
				ask.push_back(i);
			}
			else {
				upt.push_back(x);
				eraser(x);
			}
		}

		sort(ask.begin(), ask.end(), [&](int i, int j) { return query[i].ss > query[j].ss; });

		vector<int> join[BLOCK_sz];
		for(int i = L; i < R; i++) {
			int x = query[i].ff;
			int w = query[i].ss;

			if(type[i] == 1) {
				weight[x] = w;
				// cout << "weight " << x << " := " << w << endl;
			}
			else {
				for(int j : upt)
					if(weight[j] >= w)
						join[i - L].push_back(j);
			}
		}

		DSU azaa;
		set<edge>::iterator it = SET.begin();
		for(int cur : ask) { // current query ID
			const int u = query[cur].ff;
			const int w = query[cur].ss;

			while(it != SET.end() && (*it).w >= w) {
				azaa.unite((*it).u, (*it).v);
				it++;
			}

			int snap = azaa.hist.size();
			for(int j : join[cur - L]) {
				int u, v;
				tie(u, v) = edges[j];
				azaa.unite(u, v);
			}

			int p = azaa.parent(u);
			ans[cur] = -azaa.par[p];
			azaa.roll_back(snap);

			for(int i = 1; i <= n; i++) {
				int j = azaa.parent(i);
			}
		}

		for(int i : upt) {
			int u = edges[i].ff;
			int v = edges[i].ss;
			int w = weight[i];
			SET.insert(edge(i, u, v, w));
		}

		if(SET.size() > m) for(;;);
		if(SET.size() < m) return 1;
	}

	for(int i = 0; i < q; i++)
		if(type[i] == 2)
			cout << ans[i] << endl;

	#ifdef LOCAL
	auto TIME_en = chrono::steady_clock::now();
	int TIME = chrono::duration_cast<chrono::milliseconds> (TIME_en - TIME_st).count();
	cout << "----------------------------\n";
	cout << "total time: " << TIME << "ms\n";
	#endif
	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