Submission #222886

#	Time	Username	Problem	Language	Result	Execution time	Memory
222886		atoiz	Bridges (APIO19_bridges)	C++14	100 / 100	1742 ms	9724 KiB

bridges

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <set>
#include <functional>
#include <cassert>

using namespace std;

const int MAXN = 50007, MAXM = 100007, SPLIT = 320;
struct Edge { int from, to, w, nxt; } edges[MAXM], subEdges[SPLIT * 2 + 7];
int start[MAXN], numEdges;
bool vis[MAXN];
int N, M, Q, ans[MAXM];
vector<pair<int, int>> sortedEdges, changedEdges, tmp;
vector<tuple<int, int, int>> changes, queries;

vector<int> singleChanges[MAXM];
int changePos[MAXM];
bool changed[MAXM];

namespace dsu {
	int arr[MAXN];
	void reset() { fill_n(arr + 1, N, -1); } 
	int root(int u) { return (arr[u] < 0 ? u : arr[u] = root(arr[u])); }
	void join(int u, int v)
	{
		u = root(u), v = root(v);
		if (u == v) return;
		if (arr[u] > arr[v]) swap(u, v);
		arr[u] += arr[v];
		arr[v] = u;
	}
	int sizeOf(int u) { return -arr[root(u)]; }
}

inline void addEdge(int from, int to) {
	subEdges[++numEdges] = {from, to, 0, start[from]};
	start[from] = numEdges;
}

int curAns;
void dfs(int u) {
	curAns += dsu::sizeOf(u);
	vis[u] = true;
	for (int i = start[u]; i > 0; i = subEdges[i].nxt) {
		int v = subEdges[i].to;
		if (!vis[v]) dfs(v);
	}
}

void solve()
{
	dsu::reset();

	for (auto change : changes) {
		int edgeId, newW;
		tie(edgeId, newW, ignore) = change;

		singleChanges[edgeId].push_back(newW);
		changed[edgeId] = true;
	}

	sort(queries.begin(), queries.end(), [&](tuple<int, int, int> &lhs, tuple<int, int, int> &rhs) { return get<1>(lhs) > get<1>(rhs); });
	auto e_it = sortedEdges.rbegin();
	auto c_it = changes.begin();
	for (auto query : queries) {
		int source, w, id;
		tie(source, w, id) = query;
		for (; e_it != sortedEdges.rend() && e_it -> first >= w; ++e_it) if (!changed[e_it -> second]) {
			auto &edge = edges[e_it -> second];
			dsu::join(edge.from, edge.to);
		}

		for (; c_it != changes.end() && get<2>(*c_it) < id; ++c_it) ++changePos[get<0>(*c_it)];
		for (; c_it != changes.begin() && get<2>(*prev(c_it)) > id; --c_it) --changePos[get<0>(*prev(c_it))];

		numEdges = 0;
		for (auto &change : changes) {
			int edgeId = get<0>(change);
			int u = dsu::root(edges[edgeId].from), v = dsu::root(edges[edgeId].to);
			int newW = (changePos[edgeId] ? singleChanges[edgeId][changePos[edgeId] - 1] : edges[edgeId].w);
			if (newW >= w) {
				addEdge(u, v);
				addEdge(v, u);
			}
		}

		curAns = 0;
		dfs(dsu::root(source));
		ans[id] = curAns;

		vis[dsu::root(source)] = 0;
		for (auto change : changes) {
			int edgeId = get<0>(change);
			int u = dsu::root(edges[edgeId].from), v = dsu::root(edges[edgeId].to);
			start[u] = start[v] = 0;
			vis[u] = vis[v] = 0;
		}
	}

	changedEdges.clear();
	for (int edgeId = 1; edgeId <= M; ++edgeId) if (changed[edgeId]) {
		changedEdges.emplace_back(edges[edgeId].w = singleChanges[edgeId].back(), edgeId);
	}
	sort(changedEdges.begin(), changedEdges.end());
	tmp.clear();
	for (auto it1 = changedEdges.begin(), it2 = sortedEdges.begin(); it1 != changedEdges.end() || it2 != sortedEdges.end(); ) {
		for (; it2 != sortedEdges.end() && changed[it2 -> second]; ++it2);
		if (it1 != changedEdges.end() && (it2 == sortedEdges.end() || (*it1) < (*it2))) {
			tmp.push_back(*(it1++));
		} else if (it2 != sortedEdges.end()) {
			tmp.push_back(*(it2++));
		}
	}
	tmp.swap(sortedEdges);

	for (auto change : changes) {
		int edgeId, newW;
		tie(edgeId, newW, ignore) = change;

		singleChanges[edgeId].clear();
		changePos[edgeId] = 0;
		changed[edgeId] = false;
	}

	changes.clear();
	queries.clear();
}

int main()
{
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; ++i) {
		auto &x = edges[i];
		cin >> x.from >> x.to >> x.w;
		sortedEdges.emplace_back(x.w, i);
	}
	sort(sortedEdges.begin(), sortedEdges.end());

	cin >> Q;
	changes.reserve(SPLIT);
	queries.reserve(Q);
	for (int i = 0; i < Q; ++i) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t == 1) changes.emplace_back(x, y, i);
		else queries.emplace_back(x, y, i);

		if (changes.size() == SPLIT) solve();
	}
	solve();

	for (int i = 0; i < Q; ++i) {
		if (ans[i]) cout << ans[i] << '\n';
	}

	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}

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