제출 #1129826

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

riggedroads

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

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) {
		while (pos<bit.size()) {
			bit[pos] += val;
			pos += pos&-pos;
		}
	}

	Type Query(int 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) {
			dfs1(i,k,timer);
			last[i] = w;
			fnwk.Add(tin[i],1);
			fnwk.Add(tout[i]+1,-1);

			tout[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);
	}

	last.assign(gs+1, -1);
	{ int timer = 0; dfs1(1,0,timer); }

	int cnt = 1;
	for (int i = 0; i < edg; i++) {
		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);
			}

			if (fnwk.Query(tin[b],tin[b])<=0) {
				continue;
			}

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

#if 1
			for (auto node : {a, b}) {
				while (depth[node]>depth[lca]) {
					//std::cerr << node << "\n";
					int ret = -1;
					int l = 0, r = depth[node]-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) {
						ans[last[ret]] = cnt++;
						fnwk.Add(tin[ret],-1);
						fnwk.Add(tout[ret]+1,1);
						node = up[0][ret];
					}
					else {
						node = lca;
					}
				}
			}

			ans[i] = cnt++;
			fnwk.Add(tin[b],-1);
			fnwk.Add(tout[b]+1,1);
#endif
		}
	}

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

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