Submission #257755

#	Time	Username	Problem	Language	Result	Execution time	Memory
257755		Evirir	Valley (BOI19_valley)	C++17	100 / 100	445 ms	39144 KiB

valley

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

class LazySegmentTree{
private:
	int size_;
	vector<ll> v,lazy;
	
	void update(int s, int e, ll val, int k, int l, int r){
		push(k, l, r);
		if(r < s || e < l) return;
		if(s <= l && r <= e){
			lazy[k] += val;
			push(k, l, r);
		}
		else{
			update(s, e, val, k*2, l, (l+r)>>1);
			update(s, e, val, k*2+1, ((l+r)>>1)+1, r);
			v[k] = merge(v[k*2], v[k*2+1]);
		}
	}
	
	ll query(int s, int e, int k, int l, int r){
		push(k, l, r);
		if(r < s || e < l) return INF; //dummy value
		if(s <= l && r <= e) return v[k];
		ll lc = query(s, e, k*2, l, (l+r)>>1);
		ll rc = query(s, e, k*2+1, ((l+r)>>1)+1, r);
		return merge(lc, rc);
	}
 
public:
	LazySegmentTree(): v(vector<ll>()), lazy(vector<ll>()) {}
	LazySegmentTree(int n){
		for(size_=1;size_<n;) size_<<=1;
		v.resize(size_*4);
		lazy.resize(size_*4);
	}
	void reset(){
		v.assign(size_*4,0);
		lazy.assign(size_*4,0);
	}
	inline void push(int k, int l, int r){
		if(lazy[k]!=0){
			v[k] += lazy[k];	//remember to consider the range!
			if(l!=r){
				lazy[k*2]+=lazy[k];
				lazy[k*2+1]+=lazy[k];
			}
			lazy[k]=0;
		}
	}
	inline ll merge(ll x, ll y){
		return min(x,y);
	}
	inline void update(int l, int r, ll val){
		update(l, r, val, 1, 0, size_-1);
	}
	inline ll query(int l, int r){
		return query(l, r, 1, 0, size_-1);
	}
};

const bool DEBUG = 0;
const int MAXN = 100005;

int n,S,Q,E;
vii adj[MAXN];
vii edges;
ll dist[MAXN];
vi shops;
LazySegmentTree st;
vii que[MAXN]; //friend location, query index
int in[MAXN],out[MAXN],tmr=-1,dep[MAXN];
ll ans[MAXN];

void dfs_euler(int u, int p)
{
	//cout<<"dfs_euler("<<u+1<<","<<p+1<<")"<<endl;
	in[u]=++tmr;
	for(ii tmp: adj[u])
	{
		int v=tmp.F; ll w=tmp.S;
		if(v==p) continue;
		dep[v]=dep[u]+1;
		dist[v]=dist[u]+w;
		dfs_euler(v,u);
	}
	out[u]=tmr;
}

void dfs(int u, int p)
{
	//cout<<"dfs("<<u+1<<","<<p+1<<")"<<endl;
	for(ii q: que[u])
	{
		int sub=q.F, id=q.S;
		
		//u is in queried subtree
		if(in[sub]<=in[u] && out[u]<=out[sub]){
			ans[id]=st.query(in[sub], out[sub]);
		}
		//outside, escaped
		else{
			ans[id]=-1;
		}
	}
	
	for(ii tmp: adj[u])
	{
		int v=tmp.F; ll w=tmp.S;
		if(v==p) continue;
		
		st.update(in[v], out[v], -w);
		st.update(0, in[v]-1, w);
		st.update(out[v]+1, n-1, w);
		
		dfs(v,u);
		
		//undo everything
		st.update(in[v], out[v], w);
		st.update(0, in[v]-1, -w);
		st.update(out[v]+1, n-1, -w);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>S>>Q>>E; E--;
	st=LazySegmentTree(n);
	
	forn(i,0,n) st.update(i,i,INF);
	
	forn(i,0,n-1){
		int u,v; ll w; cin>>u>>v>>w; u--; v--;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
		edges.pb({u,v});
	}
	
	dfs_euler(E,-1);
	
	forn(i,0,S){
		int u; cin>>u; u--;
		shops.pb(u);
		st.update(in[u], in[u], -INF+dist[u]); //distance from node E
	}
	
	forn(i,0,Q){
		int e; cin>>e; e--;
		int u=edges[e].F, v=edges[e].S;
		if(dep[u]>dep[v]) swap(u,v); //ensure v is lower (deeper)
		int f; cin>>f; f--; //friend
		que[f].pb({v,i});
	}
	
	dfs(E,-1);
	
	forn(i,0,Q){
		if(ans[i]>1e16) cout<<"oo\n";
		else if(ans[i]==-1) cout<<"escaped\n";
		else cout<<ans[i]<<'\n';
	}
	
	return 0;
}

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