Submission #1270690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270690		thuhienne	Valley (BOI19_valley)	C++20	36 / 100	3095 ms	168864 KiB

valley

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

using ll = long long;

const int LOG = 17;
const int can = 350;

int n,q,numshop,root;
int shop[100009];

vector <pair <int,int>> adj[100009];

struct {
	int u,v,w;
} edge[100009];

int h[100009];
long long depth[100009];

int tin[100009],tout[100009],timedfs;
int pos[100009],timelca,R[200009][LOG + 1];

void dfs(int node,int par) {
	tin[node] = ++timedfs;
	pos[node] = ++timelca;
	R[timelca][0] = node;
	for (auto x : adj[node]) if (x.first != par) {
		int ver = x.first,w = x.second;
		h[ver] = h[node] + 1;
		depth[ver] = depth[node] + w;
		dfs(ver,node);
		R[++timelca][0] = node;
	}
	tout[node] = timedfs;
}

bool intree(int child,int anc) {
	return tin[anc] <= tin[child] && tout[child] <= tout[anc];
}

void buildsparse() {
	for (int j = 1;j <= LOG;j++) {
		for (int i = 1;i + (1 << j) - 1 <= timelca;i++) {
			int d1 = R[i][j - 1],d2 = R[i + (1 << (j - 1))][j - 1];
			R[i][j] = (h[d1] < h[d2] ? d1 : d2);
		}
	}
}

int lca(int u,int v) {
	u = pos[u],v = pos[v];
	if (u > v) swap(u,v);
	int i = __lg(v - u + 1);
	int d1 = R[u][i],d2 = R[v - (1 << i) + 1][i];
	return (h[d1] < h[d2] ? d1 : d2);
}

long long dis(int u,int v) {
	return depth[u] + depth[v] - 2*depth[lca(u,v)];
}

struct {
	int l,r;
	long long mindis[100009];
} block[can + 1];

void djt(vector <int> start,long long l[]) {
	for (int i = 1;i <= n;i++) l[i] = 1e18;
	priority_queue <pair<ll,int>,vector <pair <ll,int>>,greater <pair <ll,int>>> pq;
	for (auto x : start) {
		l[x] = 0;
		pq.push({l[x],x});
	}
	while (pq.size()) {
		int ver = pq.top().second;
		long long cost = pq.top().first;
		pq.pop();
		if (l[ver] < cost) continue;
		for (auto x : adj[ver]) {
			int u = x.first,w = x.second;
			if (l[u] > l[ver] + w) {
				l[u] = l[ver] + w;
				pq.push({l[u],u});
			}
		}
	}
}

void precal() {
	sort(shop + 1,shop + 1 + numshop,[] (int a,int b) {
		return tin[a] < tin[b];
	});
	for (int id = 0;;id++) {
		block[id].l = max(1,id*can);
		block[id].r = min(numshop,(id + 1)*can - 1);
		vector <int> start;
		for (int i = block[id].l;i <= block[id].r;i++) start.push_back(shop[i]);
		djt(start,block[id].mindis);
		if (block[id].r == numshop) break;
	}
}

long long calc(int l,int r,int vertice) {
	if (l > r) return 1e18;
	long long ret = 1e18;
	
	int lid = l/can,rid = r/can;
	if (lid == rid) {
		for (int i = l;i <= r;i++) ret = min(ret,dis(vertice,shop[i]));
		return ret;
	}
	for (int i = l;i <= block[lid].r;i++) ret = min(ret,dis(vertice,shop[i]));
	for (int i = lid + 1;i < rid;i++) ret = min(ret,block[i].mindis[vertice]);
	for (int i = block[rid].l;i <= r;i++) ret = min(ret,dis(vertice,shop[i]));
	return ret;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);

	cin >> n >> numshop >> q >> root;
	for (int i = 1;i < n;i++) {
		int u,v,w;cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
		edge[i] = {u,v,w};
	}
	for (int i = 1;i <= numshop;i++) {
		cin >> shop[i];
	}
	dfs(root,-1);
	buildsparse();
	for (int i = 1;i < n;i++) if (h[edge[i].u] > h[edge[i].v]) swap(edge[i].u,edge[i].v);
	precal();
	while (q--) {
		int vertice,_;cin >> _ >> vertice;
		int child = edge[_].v;
		//check escape
		if ((intree(vertice,child) ^ intree(root,child)) == 0) {
			cout << "escaped\n";
			continue;
		}
		//tim khong trong shop ma cay con goc child quan ly
		int l,r;
		int low = 1,high = numshop;
		while (low <= high) {
			int mid = (low + high) >> 1;
			if (tin[shop[mid]] >= tin[child]) high = mid - 1;
			else low = mid + 1;
		}
		l = low;
		low = 1,high = numshop;
		while (low <= high) {
			int mid = (low + high) >> 1;
			if (tin[shop[mid]] <= tout[child]) low = mid + 1;
			else high = mid - 1;
		}
		r = high;
		long long ret = 1e18;
		//TH1: vertice nam trong cay con goc child
		if (intree(vertice,child)) {
			ret = calc(l,r,vertice);
		}
		//TH2: vertice khong nam trong cay con goc v
		else {
			ret = min(calc(1,l - 1,vertice),calc(r + 1,n,vertice));
		}
		if (ret == 1e18) cout << "oo\n";
		else cout << ret << '\n';
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41