Submission #1164097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164097		YunGoon	오두막집 (GA7_cabana)	C++20	100 / 100	5922 ms	27076 KiB

cabana

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>

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;
	}
	
	int s = 0, e = 50000000;
	while (s <= e) {
		int m = s + e >> 1;
		
		long cnt = 0;
		bool used[100001]{};
		auto go = [&](auto& go, int now, int D) -> void {
			used[now] = 1;
			
			ordered_set S;
			vector<int> keep;
			
			auto solve = [&](auto& solve, int now, int prv, int d) -> void {
				if (used[now]) return;
				
				if (cabin[now]) {
					cnt += S.order_of_key(D - d + 1);
					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) S.insert(it);
			}
			
			if (cabin[now]) {
				cnt += S.order_of_key(D + 1);
			}
			
			for (int nxt : cent.adj[now]) {
				if (used[nxt]) continue;
				go(go, nxt, D);
			}
		};
		
		go(go, root, m);
		
		if (cnt < K) s = m + 1;
		else e = m - 1;
	}
	
	cout << s;

	return 0;
}

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