제출 #237573

#제출 시각아이디문제언어결과실행 시간메모리
237573grtValley (BOI19_valley)C++17
0 / 100
249 ms23128 KiB
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

struct Query {
	int id, block;
};

struct Edge {
	int v, cost, id;
};

struct Node {
	ll f, g;
};

const int nax = 100 * 1000 + 10;
const ll INF = (ll)1e16+10;
int n,q,s,root,nr;
int in[nax], out[nax];
int edge_block[nax];
ll dist[nax];
bool is_shop[nax];
vector<Query>qr[nax];
vector<Edge>V[nax];
Node T[(1<<18)];
ll ans[nax];

void propagate(int x) {
	T[2*x].g += T[x].g;
	T[2*x+1].g += T[x].g;
	T[x].g = 0;
}

void update(int a,int b, ll x, int l, int r, int v) {
	//~ cout << a << " " << b << ": "<<l << " " << r << "\n";
	if(a <= l && r <= b) {
		T[v].g += x;
		return;
	}
	propagate(v);
	int mid = (l+r)/2;
	if(a <= mid) update(a,b,x,l,mid,v*2);
	if(mid < b) update(a,b,x,mid+1,r,v*2+1);
	T[v].f = min(T[2*v].f + T[2*v].g, T[2*v+1].f + T[2*v+1].g);
}

ll query(int a,int b,int l, int r, int v) {
	//~ cout << l << " " << r << "\n";
	if(a <= l && r <= b) {
		return T[v].f + T[v].g;
	}
	propagate(v);
	int mid = (l+r)/2;
	ll w = INF;
	if(a <= mid) w = min(w, query(a,b,l,mid,v*2));
	if(mid < b) w = min(w, query(a,b,mid+1,r,v*2+1));
	return w + T[v].g;
}


void dfs(int x, int p) {
	in[x] = nr++;
	for(auto nbh : V[x]) {
		if(nbh.v != p) {
			edge_block[nbh.id] = nbh.v;
			dist[nbh.v] = dist[x] + nbh.cost;
			dfs(nbh.v, x);
		}
	}
	out[x] = nr;
}

void dfsAns(int x,int p) {
	for(auto qre : qr[x]) {
		int v = edge_block[qre.block];
		if(in[v] <= in[x] && in[x] <= out[v] - 1) {
			//~ cout << "X\n";
			ll d = query(in[v], out[v] - 1, 0, n-1, 1);
			//~ cout << "D : "<<d << "\n";
			ans[qre.id] = d;
		} else {
			ans[qre.id] = -1;
		}
	}
	//~ cout << x << "\n";
	for(auto nbh : V[x]) {
		if(nbh.v != p) {
			//~ cout << in[nbh.v] << " " << out[nbh.v] << "\n";
			update(in[nbh.v], out[nbh.v] - 1, -2 * nbh.cost, 0, n-1, 1);
			update(0, n-1, nbh.cost, 0, n-1, 1);
			dfsAns(nbh.v, x);
			update(in[nbh.v], out[nbh.v] - 1, 2 * nbh.cost, 0, n-1, 1);
			update(0, n-1, -nbh.cost, 0, n-1, 1);
		}
	}
}

void init(int l, int r, int v) {
	T[v].f = INF;
	if(l == r) {
		return;
	}
	init(l, (l+r)/2, v*2);
	init((l+r)/2 + 1, r, v*2+1);
}

int main() {_
	cin >> n >> s >> q >> root;
	for(int a,b,w,i=1; i < n; ++i) {
		cin >> a >> b >> w;
		V[a].PB({b,w,i});
		V[b].PB({a,w,i});
	}
	for(int a,i = 1; i <= s; ++i) {
		cin >> a;
		is_shop[a] = 1;
	}
	for(int a,b,i=1; i<= q; ++i) {
		cin >> a >> b;
		qr[b].PB({i,a});
	}
	dfs(root, 0);
	//~ init(0, n-1, 1);
	for(int i = 1; i <= n; ++i) {
		//~ cout << "I : " << in[i] << " " << out[i] << "\n";
		if(is_shop[i]) {
			update(in[i], in[i], dist[i], 0, n-1, 1);
		} else {
			update(in[i], in[i], INF, 0, n-1, 1);
		}
	}
	dfsAns(root, 0);
	for(int i = 1; i <= q; ++i) {
		if(ans[i] == -1) {
			cout << "escaped\n";
		} else if(ans[i] > (ll)1e14) {
			cout << "oo\n";
		} else {
			cout << ans[i] << "\n";
		}
	}
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...