제출 #1129860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129860		xnqs	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	1063 ms	62876 KiB

riggedroads

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
#include <cassert>

template<typename Type>
class FenwickTree {
private:
	std::vector<Type> bit;
public:
	FenwickTree(int size = 0, Type val = 0) {
		Assign(size,val);
	}

	void Assign(int size = 0, Type val = 0) {
		bit.assign(size, 0);
		for (int i = 1; i < size; i++) {
			bit[i] += val;
			if (i+(i&-i)<size) {
				bit[i+(i&-i)] += bit[i];
			}
		}
	}

	void Add(int pos, Type val) {
		++pos;
		while (pos<bit.size()) {
			bit[pos] += val;
			pos += pos&-pos;
		}
	}

	Type Query(int pos) {
		++pos;
		Type ret = 0;
		while (pos>0) {
			ret += bit[pos];
			pos ^= pos&-pos;
		}
		return ret;
	}

	Type Query(int l, int r) {
		return Query(r) - Query(l-1);
	}
};

int gs, edg;
std::vector<std::vector<std::pair<int,int>>> adj_list;
std::vector<std::pair<int,int>> edges;
std::vector<int> mst_edg_idx;
std::vector<int> last;
int depth[300005];
int up[19][300005];
int tin[300005];
int tout[300005];
int ans[300005];
FenwickTree<int> fnwk;

void dfs1(int k, int p, int& timer) {
	depth[k] = depth[p]+1;
	tin[k] = ++timer;
	up[0][k] = p;
	for (int j = 1; j < 19; j++) {
		up[j][k] = up[j-1][up[j-1][k]];
	}
	for (const auto& [i, w] : adj_list[k]) {
		if (i!=p) {
			last[i] = w;
			dfs1(i,k,timer);
		}
	}
	tout[k] = ++timer;
}

int get_kth_ancestor(int node, int k) {
	while (k) {
		int lvl = 31-__builtin_clz(k);
		node = up[lvl][node];
		k ^= (1<<lvl);
	}
	return node;
}

int get_lca(int a, int b) {
	if (depth[a]>depth[b]) {
		std::swap(a,b);
	}

	b = get_kth_ancestor(b, depth[b]-depth[a]);

	for (int lvl = 18; a!=b;) {
		while (lvl-1>=0&&up[lvl][a]==up[lvl][b]) {
			--lvl;
		}
		a = up[lvl][a];
		b = up[lvl][b];
	}
	return a;
}

inline int root_path_query(int k) {
	return fnwk.Query(tin[k]);
}

inline int path_query(int a, int b) {
	return root_path_query(a) + root_path_query(b) - 2*root_path_query(up[0][get_lca(a,b)]);
}

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

	std::cin >> gs >> edg;
	fnwk.Assign(2*gs+5,0);
	adj_list.resize(gs+1);
	edges.reserve(edg);
	mst_edg_idx.reserve(gs-1);

	for (int i = 0, a, b; i < edg; i++) {
		std::cin >> a >> b;
		edges.emplace_back(a,b);
	}

	for (int i = 0, tmp; i < gs-1; i++) {
		std::cin >> tmp; --tmp;
		mst_edg_idx.emplace_back(tmp);

		auto [a, b] = edges[tmp];
		adj_list[a].emplace_back(b,tmp);
		adj_list[b].emplace_back(a,tmp);
	}

	// kys
	std::sort(mst_edg_idx.begin(),mst_edg_idx.end());

	last.assign(gs+1, -1);
	{ int timer = 0; dfs1(1,0,timer); }
	for (int i = 2; i <= gs; i++) {
		fnwk.Add(tin[i],1);
		fnwk.Add(tout[i],-1);
	}

	int cnt = 1;
	std::vector<bool> solved(edg,0);
	for (int i = 0; i < edg; i++) {
		if (solved[i]) {
			continue;
		}

		if (std::binary_search(mst_edg_idx.begin(),mst_edg_idx.end(),i)) {
			auto [a, b] = edges[i];
			if (depth[a]>depth[b]) {
				std::swap(a,b);
			}

			solved[i] = 1;
			ans[i] = cnt++;
			fnwk.Add(tin[b],-1);
			fnwk.Add(tout[b],1);
			//std::cout << i << " " << ans[i] << "\n";
		}
		else {
			auto [a, b] = edges[i];
			int lca = get_lca(a,b);
			std::vector<int> nodes;

			for (auto node : {a, b}) {
				while (depth[node]>depth[lca]) {
					int ret = -1;
					int l = 0, r = depth[node]-depth[lca]-1;
					while (l<=r) {
						int m = (l+r)>>1;
						int kth_ancestor = get_kth_ancestor(node,m);
						if (root_path_query(node) - root_path_query(up[0][kth_ancestor])) {
							ret = kth_ancestor;
							r = m-1;
						}
						else {
							l = m+1;
						}
					}

					if (ret!=-1) {
						fnwk.Add(tin[ret],-1);
						fnwk.Add(tout[ret],1);
						nodes.emplace_back(ret);
						node = up[0][ret];
					}
					else {
						node = lca;
					}
				}
			}

			std::sort(nodes.begin(),nodes.end(),[&](int a, int b) {
				return last[a] < last[b];
			});

			for (const auto& node : nodes) {
				assert(node!=1);
				int edge = last[node];
				solved[edge] = 1;
				ans[edge] = cnt++;
			}

			solved[i] = 1;
			ans[i] = cnt++;
		}
	}

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

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32