oj.uz

Submission #545805

# Submission time Handle Problem Language Result Execution time Memory
545805 2022-04-05T13:18:06 Z jamezzz Valley (BOI19_valley) C++17
100 / 100
 2930 ms 227852 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ll> il;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 100005

struct node{
	int n;
	vector<ll> lz;
	vector<il> v;
	void init(int _n){
		n=_n;
		v.resize(4*n,{0,0});
		lz.resize(4*n,0);
	}
	void ppo(int i,int s,int e){
		v[i].se+=lz[i];
		if(s!=e){
			lz[2*i+1]+=lz[i];
			lz[2*i+2]+=lz[i];
		}
		lz[i]=0;
	}
	void up(int i,int s,int e,int x,int y,ll nv){
		if(s==x&&e==y){
			lz[i]+=nv;return;
		}
		int m=(s+e)>>1;
		if(y<=m)up(2*i+1,s,m,x,y,nv);
		else if(x>m)up(2*i+2,m+1,e,x,y,nv);
		else up(2*i+1,s,m,x,m,nv),up(2*i+2,m+1,e,m+1,y,nv);
		ppo(2*i+1,s,m);ppo(2*i+2,m+1,e);
		v[i]=min(v[2*i+1],v[2*i+2]);
	}
	void up(int x,int y,ll nv){
		up(0,0,n-1,x,y,nv);
	}
	void set(int i,int s,int e,int x,int t){
		if(s==x&&e==x){
			v[i].fi=t;return;
		}
		int m=(s+e)>>1;
		if(x<=m)set(2*i+1,s,m,x,t);
		else set(2*i+2,m+1,e,x,t);
		ppo(2*i+1,s,m);ppo(2*i+2,m+1,e);
		v[i]=min(v[2*i+1],v[2*i+2]);
	}
	void set(int x,int t){
		set(0,0,n-1,x,t);
	}
	il qry(int i,int s,int e,int x,int y){
		ppo(i,s,e);
		if(s==x&&e==y)return v[i];
		int m=(s+e)>>1;
		if(y<=m)return qry(2*i+1,s,m,x,y);
		if(x>m)return qry(2*i+2,m+1,e,x,y);
		return min(qry(2*i+1,s,m,x,m),qry(2*i+2,m+1,e,m+1,y));
	}
	il qry(int x,int y){
		if(x>y)return {2,LINF};
		return qry(0,0,n-1,x,y);
	}
}seg[maxn];

int n,q,s,e,w[maxn],sub[maxn];
vii AL[maxn];
bool shop[maxn],done[maxn];
vi nodeComp[maxn],edgeComp[maxn];
vii nodeRange[maxn],edgeRange[maxn];
ii block[maxn];
int cnt;

void calc(int u,int p){
	sub[u]=1;
	for(auto[v,i]:AL[u]){
		if(v==p||done[v])continue;
		calc(v,u);
		sub[u]+=sub[v];
	}
}

void dfs(int u,int p,int c){
	ii rng={cnt,cnt};++cnt;
	for(auto[v,i]:AL[u]){
		if(v==p||done[v])continue;
		dfs(v,u,c);
		ii tmp=nodeRange[v].back();
		rng.se=max(rng.se,tmp.se);
		edgeComp[i].pb(c);
		edgeRange[i].pb(tmp);
	}
	nodeComp[u].pb(c);
	nodeRange[u].pb(rng);
}

void decomp(int u){
	calc(u,-1);
	int c=u;
	while(true){
		bool val=true;
		for(auto[v,i]:AL[c]){
			if(done[v])continue;
			if(sub[v]<sub[c]&&sub[v]>sub[u]/2){
				c=v;val=false;
			}
		}
		if(val)break;
	}
	
	cnt=0;
	dfs(c,-1,c);
	seg[c].init(cnt);
	
	done[c]=true;
	for(auto[v,i]:AL[c]){
		if(!done[v])decomp(v);
	}
}

int main(){
	n=rd();s=rd();q=rd();e=rd();
	for(int i=1;i<n;++i){
		int a=rd(),b=rd();
		w[i]=rd();
		AL[a].pb({b,i});
		AL[b].pb({a,i});
	}
	for(int i=0;i<s;++i){
		int c=rd();
		shop[c]=true;
	}
	
	decomp(1);
	
	for(int i=1;i<n;++i){
		for(int j=0;j<sz(edgeComp[i]);++j){
			int c=edgeComp[i][j];
			ii r=edgeRange[i][j];
			seg[c].up(r.fi,r.se,w[i]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<sz(nodeComp[i]);++j){
			int c=nodeComp[i][j];
			ii r=nodeRange[i][j];
			if(i==e)seg[c].set(r.fi,0);
			else if(shop[i])seg[c].set(r.fi,1);
			else seg[c].set(r.fi,2);
		}
	}
	
	for(int i=1;i<=n;++i)block[i]={seg[i].n,-1};
	
	for(int i=0;i<q;++i){
		int x=rd(),s=rd();
		
		for(int i=0;i<sz(edgeComp[x]);++i){
			block[edgeComp[x][i]]=edgeRange[x][i];
		}
		
		ll ans=LINF;
		for(int i=0;i<sz(nodeComp[s]);++i){
			int c=nodeComp[s][i];
			ii r=nodeRange[s][i];
			if(block[c].fi<=r.fi&&r.fi<=block[c].se)continue;//path to this is blocked
			il d1=seg[c].qry(r.fi,r.fi);
			if(d1.fi==0)ans=-1;
			else if(d1.fi==1)ans=min(ans,0ll);
			il d2=min(seg[c].qry(0,block[c].fi-1),seg[c].qry(block[c].se+1,seg[c].n-1));
			if(d2.fi==0)ans=-1;
			else if(d2.fi==1)ans=min(ans,d1.se+d2.se);
		}
		
		for(int i=0;i<sz(edgeComp[x]);++i){
			int c=edgeComp[x][i];
			block[c]={seg[c].n,-1};
		}
		
		if(ans==LINF)pf("oo\n");
		else if(ans==-1)pf("escaped\n");
		else pf("%lld\n",ans);
	}
}

/*
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17748 KB Output is correct
2 Correct 15 ms 17720 KB Output is correct
3 Correct 15 ms 17688 KB Output is correct
4 Correct 15 ms 17684 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17748 KB Output is correct
2 Correct 15 ms 17720 KB Output is correct
3 Correct 15 ms 17688 KB Output is correct
4 Correct 15 ms 17684 KB Output is correct
5 Correct 11 ms 18116 KB Output is correct
6 Correct 14 ms 18388 KB Output is correct
7 Correct 15 ms 18644 KB Output is correct
8 Correct 12 ms 18132 KB Output is correct
9 Correct 14 ms 18376 KB Output is correct
10 Correct 15 ms 18712 KB Output is correct
11 Correct 12 ms 18204 KB Output is correct
12 Correct 18 ms 18424 KB Output is correct
13 Correct 15 ms 18644 KB Output is correct
14 Correct 15 ms 18580 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 974 ms 97540 KB Output is correct
2 Correct 1608 ms 146508 KB Output is correct
3 Correct 2126 ms 179184 KB Output is correct
4 Correct 2632 ms 207956 KB Output is correct
5 Correct 2641 ms 208644 KB Output is correct
6 Correct 2730 ms 227852 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17748 KB Output is correct
2 Correct 15 ms 17720 KB Output is correct
3 Correct 15 ms 17688 KB Output is correct
4 Correct 15 ms 17684 KB Output is correct
5 Correct 11 ms 18116 KB Output is correct
6 Correct 14 ms 18388 KB Output is correct
7 Correct 15 ms 18644 KB Output is correct
8 Correct 12 ms 18132 KB Output is correct
9 Correct 14 ms 18376 KB Output is correct
10 Correct 15 ms 18712 KB Output is correct
11 Correct 12 ms 18204 KB Output is correct
12 Correct 18 ms 18424 KB Output is correct
13 Correct 15 ms 18644 KB Output is correct
14 Correct 15 ms 18580 KB Output is correct
15 Correct 974 ms 97540 KB Output is correct
16 Correct 1608 ms 146508 KB Output is correct
17 Correct 2126 ms 179184 KB Output is correct
18 Correct 2632 ms 207956 KB Output is correct
19 Correct 2641 ms 208644 KB Output is correct
20 Correct 2730 ms 227852 KB Output is correct
21 Correct 930 ms 97308 KB Output is correct
22 Correct 1654 ms 150040 KB Output is correct
23 Correct 2074 ms 180112 KB Output is correct
24 Correct 2697 ms 207868 KB Output is correct
25 Correct 2892 ms 226336 KB Output is correct
26 Correct 964 ms 101168 KB Output is correct
27 Correct 1607 ms 149840 KB Output is correct
28 Correct 2208 ms 186588 KB Output is correct
29 Correct 2603 ms 211536 KB Output is correct
30 Correct 2930 ms 226432 KB Output is correct
31 Correct 922 ms 99616 KB Output is correct
32 Correct 1636 ms 154804 KB Output is correct
33 Correct 2179 ms 183052 KB Output is correct
34 Correct 2636 ms 211016 KB Output is correct
35 Correct 2868 ms 226164 KB Output is correct
36 Correct 2191 ms 188232 KB Output is correct