Submission #255733

#	Time	Username	Problem	Language	Result	Execution time	Memory
255733		Blagojce	Valley (BOI19_valley)	C++11	100 / 100	650 ms	40184 KiB

valley

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
const int i_inf = 1e4;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 200005;
 
int n, s, q, E;
int edl[mxn], edr[mxn];
vector<pii> g[mxn];
bool shop[mxn];
int sz[mxn];
int pos[mxn];
int temp_pos = 0;
 
ll dist[mxn];
 
int sparse[mxn][20];
int depth[mxn];
int id[mxn];
void dfs(int u, int p){
	id[temp_pos] = u;
	pos[u] = temp_pos++;
	
	sz[u] = 1;
	
	sparse[u][0] = p;
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
	
	for(auto e : g[u]){
		if(e.st == p) continue;
		depth[e.st] = depth[u]+1;
		dist[e.st] = dist[u]+e.nd;
		dfs(e.st, u);
		sz[u] += sz[e.st];
		
	}
}
int lca(int a, int b){
	int d = min(depth[a], depth[b]);
	for(int i = 19; i >= 0; i --){
		if(depth[a]-(1<<i)>= d) a = sparse[a][i];
		if(depth[b]-(1<<i)>= d) b = sparse[b][i];
	}
	if(a == b) return a;
	for(int i = 19; i >= 0; i --){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	return sparse[a][0];
}
ll seg[4*mxn];
ll zet[4*mxn];
void build(int k, int l, int r){
	if(l == r){
		seg[k] = dist[id[l]];
		return;
	}
	int mid = (l+r)/2;
	build(k*2, l, mid);
	build(k*2+1, mid+1, r);
	seg[k] = min(seg[k*2], seg[k*2+1]);
	
}
void update(int k, int l, int r, int x, int y, ll z, ll val){
	zet[k] += z;
	if(y < l || r < x) return;
	if(x <= l && r <= y){
		zet[k] += val;
		return;
	}
	int mid = (l+r)/2;
	update(k*2, l, mid, x, y, zet[k], val);
	update(k*2+1, mid+1, r, x, y, zet[k], val);
	zet[k] = 0;
	seg[k] = min(seg[k*2]+zet[k*2], seg[k*2+1]+zet[k*2+1]);
}
ll query(int k, int l, int r, int x, int y, ll z){
	zet[k] += z;
	if(y < l || r < x) return inf;
	if(x <= l && r <= y){
		return seg[k]+zet[k];
	}
	int mid = (l+r)/2;
	ll ret = min(query(k*2, l, mid, x, y, zet[k]), query(k*2+1, mid+1, r, x, y, zet[k]));
	zet[k] = 0;
	seg[k] = min(seg[k*2]+zet[k*2], seg[k*2+1]+zet[k*2+1]);
	return ret;	
}
 
vector<int> Q[mxn];
ll ans[mxn];
 
int ed[mxn];
void dfs2(int u, int p){
	for(auto i : Q[u]){
		int q = ed[i];
		int a=edl[q], b = edr[q];
		if(depth[a] > depth[b]) swap(a, b);
		if(lca(b, u) != b){
			ans[i] = -1;
			continue;
		}
		ans[i] = query(1, 0, n-1, pos[b], pos[b]+sz[b]-1, 0);
	}
	for(auto e : g[u]){
		if(e.st == p) continue;
		int l = pos[e.st];
		int r = pos[e.st]+sz[e.st]-1;
		update(1, 0, n-1, 0, n-1, 0, e.nd);
		update(1, 0, n-1, l, r, 0, -2*e.nd);
		dfs2(e.st, u);
		update(1, 0, n-1, 0, n-1, 0, -e.nd);
		update(1, 0, n-1, l, r, 0, +2*e.nd);
	}
}
void solve(){
	cin >> n >> s >> q >> E;
	--E;
	fr(i, 0, n-1){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		g[u].pb({v, w});
		g[v].pb({u, w});
		edl[i] = u, edr[i] = v;
	}
	fr(i, 0, s){
		int c;
		cin >> c;
		--c;
		shop[c] = true;
	}
	dfs(E, E);
	fr(i, 0, n){
		if(shop[i]) continue;
		dist[i] = inf;
	}
	build(1, 0, n-1);	
	
	fr(i, 0, q){
		int e, u;
		cin >> e >> u;
		--e, --u;
		ed[i] = e;
		Q[u].pb(i);
	}
	dfs2(E, E);
	fr(i, 0, q){
		if(ans[i] == -1) cout<<"escaped"<<endl;
		else if(ans[i] >= inf/2) cout<<"oo"<<endl;
		else cout<<ans[i]<<endl;
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

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