제출 #1164104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164104		YunGoon	오두막집 (GA7_cabana)	C++20	19 / 100	6094 ms	40788 KiB

cabana

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

template<typename T>
struct DynamicSegmentTree {
	struct Node {
		int l, r, v;
		Node(int l = -1, int r = -1, int v = 0): l(l), r(r), v(v) {}
	};
	vector<Node> tree;
 
	int SZ;
	T id;

	DynamicSegmentTree(int sz, const T& id) {
		SZ = sz;
		this->id = id;
		
		tree.emplace_back(-1, -1, id);
	}
	
	void update(int idx, const T& val) {
		update(idx, val, 0, 0, SZ - 1);
	}

	T query(int L, int R) {
		return query(L, R, 0, 0, SZ - 1);
	}

private:
	void update(int idx, const T& val, int node, int s, int e) {
		if (e < idx || idx < s) return;
		if (s == e) {
			tree[node].v += val;
			return;
		}
		
		int m = s + e >> 1;
		
		if (tree[node].l == -1) {
			tree[node].l = tree.size();
			tree.emplace_back(-1, -1, id);
		}
		if (tree[node].r == -1) {
			tree[node].r = tree.size();
			tree.emplace_back(-1, -1, id);
		}
		
		update(idx, val, tree[node].l, s, m);
		update(idx, val, tree[node].r, m + 1, e);
		
		tree[node].v = tree[tree[node].l].v + tree[tree[node].r].v;
	}
	
	T query(int L, int R, int node, int s, int e) {
		if (node == -1 || e < L || R < s) return id;
		if (L <= s && e <= R) return tree[node].v;
		
		int m = s + e >> 1;
		return combine(query(L, R, tree[node].l, s, m), query(L, R, tree[node].r, m + 1, e));
	}

	T combine(const T& a, const T& b) {
		return a + b;
	}
};

struct Centroid {
	vector<vector<int>> adj;
	vector<vector<pair<int, int>>> org;
	vector<int> pa;
	
	Centroid(int N): sz(N), vis(N), org(N), adj(N), pa(N) {}
	
	void add_edge(int a, int b, int w) {
		org[a].emplace_back(b, w);
		org[b].emplace_back(a, w);
	}
	
	int build_tree(int now, int prv = 0) {
		now = get_centroid(now, prv, get_sz(now));
		vis[now] = 1;
		pa[now] = prv;
		
		for (auto [nxt, w] : org[now]) {
			if (vis[nxt]) continue;
			nxt = build_tree(nxt, now);
			
			adj[now].push_back(nxt);
			adj[nxt].push_back(now);
		}
		
		return now;
	}
	
private:
	vector<int> sz;
	vector<char> vis;
	
	int get_sz(int now, int prv = 0) {
		sz[now] = 1;
		for (auto [nxt, w] : org[now]) {
			if (nxt == prv || vis[nxt]) continue;
			sz[now] += get_sz(nxt, now);
		}
		return sz[now];
	}
	
	int get_centroid(int now, int prv, int S) {
		for (auto [nxt, w] : org[now]) {
			if (nxt == prv || vis[nxt] || sz[nxt] * 2 <= S) continue;
			return get_centroid(nxt, now, S);
		}
		return now;
	}
};

int main() {
	cin.sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N, M;
	long K;
	cin >> N >> M >> K;
	
	Centroid cent(N + 1);
	for (int R, D, i = 2; i <= N; ++i) {
		cin >> R >> D;
		cent.add_edge(i, R, D);
	}
	
	int root = cent.build_tree(1);
	
	bool cabin[100001]{};
	for (int C, i = 0; i < M; ++i) {
		cin >> C;
		cabin[C] = 1;
	}
	
	long cnt;
	bool used[100001];
	auto go = [&](auto& go, int now, int D) -> void {
		used[now] = 1;
		
		DynamicSegmentTree<int> seg(25000001, 0);
		vector<int> keep;
		
		auto solve = [&](auto& solve, int now, int prv, int d) -> void {
			if (used[now]) return;
			
			if (cabin[now]) {
				cnt += seg.query(0, D - d);
				keep.push_back(d);
			}
			
			for (auto [nxt, w] : cent.org[now]) {
				if (nxt == prv) continue;
				solve(solve, nxt, now, d + w);
			}
		};
		
		for (auto [nxt, w] : cent.org[now]) {
			keep.clear();
			solve(solve, nxt, now, w);
			for (int it : keep) seg.update(it, 1);
		}
		
		if (cabin[now]) {
			cnt += seg.query(0, D);
		}
		
		for (int nxt : cent.adj[now]) {
			if (used[nxt]) continue;
			go(go, nxt, D);
		}
	};
	
	int s = 0, e = 25000000;
	while (s <= e) {
		int m = s + e >> 1;
		
		cnt = 0;
		memset(used, 0, N + 1);
		
		go(go, root, m);
		
		if (cnt < K) s = m + 1;
		else e = m - 1;
	}
	
	cout << s;

	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 12 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37