oj.uz

Submission #564962

# Submission time Handle Problem Language Result Execution time Memory
564962 2022-05-20T05:25:53 Z inluminas Valley (BOI19_valley) C++17
100 / 100
 443 ms 50496 KB 
#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
#define l first
#define r second

const int lmt=2e5+10;
int n,s,q,e,par[lmt][20],a[lmt],idx,lvl[lmt];
vector<pair<ll,ll>>adj[lmt];
vector<pair<int,int>>ed,Q[lmt];
array<int,2>id[lmt];
bool ok[lmt];
ll mn[3*lmt],Val[lmt],ans[lmt],lazy[lmt*3];

void build(int at,int L,int R){
	if(L==R){
		mn[at]=Val[L];
		return;
	}
	int mid=(L+R)>>1;
	build(at*2,L,mid);
	build(at*2+1,mid+1,R);
	mn[at]=min(mn[at*2],mn[at*2+1]);
}

void propagate(int at,int L,int R){
	mn[at]+=lazy[at];
	if(L==R){
		lazy[at]=0;
		return;
	}
	lazy[at*2]+=lazy[at],lazy[at*2+1]+=lazy[at],lazy[at]=0;
	return;
}

void updet(int at,int L,int R,int l,int r,ll val){
	propagate(at,L,R);
	if(r<L || R<l || r<l) return;
	if(l<=L && R<=r){
		lazy[at]+=val;
		propagate(at,L,R);
		return;
	}
	int mid=(L+R)>>1;
	updet(at*2,L,mid,l,r,val);
	updet(at*2+1,mid+1,R,l,r,val);
	mn[at]=min(mn[at*2],mn[at*2+1]);
}

ll query(int at,int L,int R,int l,int r){
	propagate(at,L,R);
	if(r<L || R<l || r<l) return (ll)1e16;
	if(l<=L && R<=r) return mn[at];
	int mid=(L+R)>>1;
	return min(query(at*2,L,mid,l,r),query(at*2+1,mid+1,R,l,r));
}

void dfs(int u,int p){
	a[++idx]=u;
	for(auto [v,w]:adj[u]){
		if(v==p) continue;
		par[v][0]=u,lvl[v]=lvl[u]+1;
		dfs(v,u);
	}
	a[++idx]=u;
}

void dfS(int u,int p,ll val){
	if(ok[u]){
		Val[id[u][0]]=val,Val[id[u][1]]=val;
	}else{
		Val[id[u][0]]=1e16,Val[id[u][1]]=1e16;
	}

	for(auto [v,w]:adj[u]){
		if(v==p) continue;
		ll val2=val+w;
		dfS(v,u,val2);
	}
}

ll lca(ll p,ll q){
  if(lvl[p]<lvl[q]) swap(p,q);
  for(ll i=19;i>=0;i--){
    if(lvl[p]-(1<<i)>=lvl[q]){
      p=par[p][i];
    }
  }
  if(p==q) return p;
  for(ll i=19;i>=0;i--){
    if(par[p][i]!=-1 && par[p][i]!=par[q][i]){
      p=par[p][i],q=par[q][i];
    }
  }
  return par[p][0];
}

ll Up(ll p,ll val){
	for(ll j=19;j>=0;j--){
		if(val>=(1<<j) && par[p][j]!=-1){
			p=par[p][j];
			val-=(1<<j);
		}
	}
	return p;
}

bool yes(ll o,ll p,ll q){
	ll l=lca(p,q);
 
	if(lvl[l]<=lvl[o] && lvl[o]<=lvl[p] && o==Up(p,lvl[p]-lvl[o])) return true;
	else if(lvl[l]<=lvl[o] && lvl[o]<=lvl[q] && o==Up(q,lvl[q]-lvl[o])) return true;
	return false;
}

void Dfs(int u,int p){
	for(auto [ID,i]:Q[u]){
		int U=ed[ID-1].l,V=ed[ID-1].r;

		if(!yes(U,u,e) || !yes(V,u,e)){
			ans[i]=-1;
			continue;
		}

		if(yes(U,1,u) && yes(V,1,u)){
			if(lvl[U]<lvl[V]) swap(U,V);

			updet(1,1,n+n,1,n+n,2e15);
			updet(1,1,n+n,id[U][0],id[U][1],-2e15);

			ans[i]=query(1,1,n+n,1,n+n);

			updet(1,1,n+n,1,n+n,-2e15);
			updet(1,1,n+n,id[U][0],id[U][1],2e15);
		}else{
			if(lvl[U]<lvl[V]) swap(U,V);

			updet(1,1,n+n,id[U][0],id[U][1],2e15);

			ans[i]=query(1,1,n+n,1,n+n);

			updet(1,1,n+n,id[U][0],id[U][1],-2e15);
		}
	}

	for(auto [v,w]:adj[u]){
		if(v==p) continue;

		updet(1,1,n+n,1,n+n,w);
		updet(1,1,n+n,id[v][0],id[v][1],-w-w);

		Dfs(v,u);

		updet(1,1,n+n,id[v][0],id[v][1],+w+w);
		updet(1,1,n+n,1,n+n,-w);
	}
}

int main(){
	fastio;

	cin>>n>>s>>q>>e;
	for(int i=0;i<=n;i++){
		for(int j=0;j<20;j++) par[i][j]=-1;
	}
	for(int i=1;i<n;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
		ed.push_back({u,v});
	}
	dfs(1,0);

	for(int i=1;i<=s;i++){
		int x;
		cin>>x;
		ok[x]=1;
	}

	for(int i=1;i<=n+n;i++){
		if(id[a[i]][0]) id[a[i]][1]=i;
		else id[a[i]][0]=i;
	}

	dfS(1,0,0);

	for(int i=1;i<=q;i++){
		int ID,u;
		cin>>ID>>u;

		Q[u].push_back({ID,i});
	}

	for(int j=1;j<20;j++){
		for(int i=1;i<=n;i++){
			if(par[i][j-1]==-1) continue;
			par[i][j]=par[par[i][j-1]][j-1];
		}
	}

	build(1,1,n+n);

	Dfs(1,0);

	for(int i=1;i<=q;i++){
		if(ans[i]==-1){
			cout<<"escaped"<<endl;
			continue;
		}

		if(ans[i]>1e15) cout<<"oo"<<endl;
		else cout<<ans[i]<<endl;
	}

	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10124 KB Output is correct
2 Correct 10 ms 10060 KB Output is correct
3 Correct 13 ms 10068 KB Output is correct
4 Correct 9 ms 10116 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10124 KB Output is correct
2 Correct 10 ms 10060 KB Output is correct
3 Correct 13 ms 10068 KB Output is correct
4 Correct 9 ms 10116 KB Output is correct
5 Correct 8 ms 10068 KB Output is correct
6 Correct 8 ms 9992 KB Output is correct
7 Correct 7 ms 10068 KB Output is correct
8 Correct 7 ms 9996 KB Output is correct
9 Correct 9 ms 10068 KB Output is correct
10 Correct 8 ms 10068 KB Output is correct
11 Correct 7 ms 10000 KB Output is correct
12 Correct 7 ms 10064 KB Output is correct
13 Correct 7 ms 10000 KB Output is correct
14 Correct 7 ms 9996 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 42716 KB Output is correct
2 Correct 306 ms 42516 KB Output is correct
3 Correct 368 ms 42432 KB Output is correct
4 Correct 380 ms 45148 KB Output is correct
5 Correct 302 ms 44336 KB Output is correct
6 Correct 354 ms 50496 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10124 KB Output is correct
2 Correct 10 ms 10060 KB Output is correct
3 Correct 13 ms 10068 KB Output is correct
4 Correct 9 ms 10116 KB Output is correct
5 Correct 8 ms 10068 KB Output is correct
6 Correct 8 ms 9992 KB Output is correct
7 Correct 7 ms 10068 KB Output is correct
8 Correct 7 ms 9996 KB Output is correct
9 Correct 9 ms 10068 KB Output is correct
10 Correct 8 ms 10068 KB Output is correct
11 Correct 7 ms 10000 KB Output is correct
12 Correct 7 ms 10064 KB Output is correct
13 Correct 7 ms 10000 KB Output is correct
14 Correct 7 ms 9996 KB Output is correct
15 Correct 302 ms 42716 KB Output is correct
16 Correct 306 ms 42516 KB Output is correct
17 Correct 368 ms 42432 KB Output is correct
18 Correct 380 ms 45148 KB Output is correct
19 Correct 302 ms 44336 KB Output is correct
20 Correct 354 ms 50496 KB Output is correct
21 Correct 307 ms 42056 KB Output is correct
22 Correct 317 ms 41836 KB Output is correct
23 Correct 317 ms 41844 KB Output is correct
24 Correct 431 ms 43760 KB Output is correct
25 Correct 307 ms 48304 KB Output is correct
26 Correct 303 ms 42112 KB Output is correct
27 Correct 297 ms 41984 KB Output is correct
28 Correct 380 ms 41920 KB Output is correct
29 Correct 388 ms 44412 KB Output is correct
30 Correct 339 ms 46768 KB Output is correct
31 Correct 319 ms 42260 KB Output is correct
32 Correct 327 ms 42152 KB Output is correct
33 Correct 322 ms 42056 KB Output is correct
34 Correct 443 ms 43976 KB Output is correct
35 Correct 352 ms 47520 KB Output is correct
36 Correct 321 ms 44464 KB Output is correct