Submission #1126612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126612		nguyenphong233	Valley (BOI19_valley)	C++20	100 / 100	419 ms	30528 KiB

valley

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long 
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e5 + 5;
const long long INF = (int)1e15;
const long long MOD = (int)1e9 + 7;

int n,s,q,ew;
struct node{
	int u,v,w;
}a[MAX];
bool food[MAX];
vector<ii> qrx[MAX];
int in[MAX],out[MAX],times,h[MAX];
vector<ii> adj[MAX];
int st[MAX << 2],lazy[MAX << 2];
int res[MAX];

void lazu(int id = 1,int l = 1,int r = n){
	if(!lazy[id])return;
	st[id] += lazy[id];
	if(l != r){
		lazy[id << 1] += lazy[id];
		lazy[id << 1 | 1] += lazy[id];
	}
	lazy[id] = 0;
}
void update(int u,int v,int val,int id = 1,int l = 1,int r = n){
	if(u > v)return;
	if(u > r || v < l)return;
	if(u <= l && r <= v){
		lazy[id] += val;
		lazu(id,l,r);
		return;
	}
	lazu(id,l,r);
	int m = l + r >> 1;
	update(u,v,val,id << 1,l,m);
	update(u,v,val,id << 1 | 1,m + 1,r);
	st[id] = min(st[id << 1],st[id << 1 | 1]);
}
int get(int u,int v,int id = 1,int l = 1,int r = n){
	if(u > r || v < l)return INF;
	lazu(id,l,r);
	if(u <= l && r <= v)return st[id];
	int m = l + r >> 1;
	return min(get(u,v,id << 1,l,m),get(u,v,id << 1 | 1,m + 1,r));
}
void dfs(int u = 1,int p = 0){
	in[u] = ++times;
	for(auto e : adj[u]){
		int v = e.X;
		int w = e.Y;
		if(v == p)continue;
		h[v] = h[u] + w;
		dfs(v,u);
	}
	out[u] = times;
}
void calc(int u = 1,int p = 0){
	for(auto e : qrx[u]){
		int id = e.Y;
		int tv = e.X;
		
		int u_ = a[tv].u;
		int v_ = a[tv].v;
		
		if(in[u_] > in[v_])swap(u_,v_);
		if(in[v_] <= in[u] && out[v_] >= in[u]){
			if(in[v_] <= in[ew] && in[ew] <= out[v_])res[id] = -1;
			else res[id] = get(in[v_],out[v_]);
		}
		else {
			if(in[v_] <= in[ew] && in[ew] <= out[v_])
				res[id] = min(get(1,in[v_] - 1),get(out[v_] + 1,n));
			else
				res[id] = -1;
		}
		
	}
	for(auto e : adj[u]){
		int v = e.X;
		int w = e.Y;
		if(v == p)continue;
		update(1,in[v] - 1,w);
		update(in[v],out[v],-w);
		update(out[v] + 1,n,w);
		calc(v,u);
		update(1,in[v] - 1,-w);
		update(in[v],out[v],+w);
		update(out[v] + 1,n,-w);
	}
}
signed main(){
	
	read();
	times = 0;
	cin >> n >> s >> q >> ew;
	for(int i = 1,u,v,w;i < n;i++){
		cin >> u >> v >> w;
		a[i] = {u,v,w};
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	for(int i = 1,x;i <= s;i++){
		cin >> x;
		food[x] = 1;
	}
	dfs();
	for(int i = 1,x,r;i <= q;i++){
		cin >> x >> r;
		qrx[r].push_back({x,i});
	}
	for(int i = 1;i <= n;i++){
		if(food[i])update(in[i],in[i],h[i]);
		else update(in[i],in[i],INF + h[i]);
	}
	calc();
	
	for(int i = 1;i <= q;i++){
		if(res[i] >= INF)cout << "oo\n";
		else if(res[i] == -1)cout << "escaped\n";
		else cout << res[i] << '\n';
	}
		
}

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