Submission #155341

#	Time	Username	Problem	Language	Result	Execution time	Memory
155341		ryansee	Valley (BOI19_valley)	C++14	100 / 100	1435 ms	105420 KiB

valley

#define LOCAL
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos((ld)-1.0))
#define MAXN (100006)
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < (ll)ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll((x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <int, ll> pi;
typedef pair <int, pair<int,int>> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;}string to_string(bool b){return (b ? "true" : "false");}template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A>string to_string(A v) {bool first = true;string res = "{";for (const auto &x : v) {if (!first) {res += ", ";}first = false;res += to_string(x);}res += "}";return res;}void degug_out() { cerr << endl; }template <typename Head, typename... Tail>void degug_out(Head H, Tail... T) {cerr << " " << to_string(H);degug_out(T...);}inline ll gcd(ll a,ll b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}
#ifdef LOCAL
#define degug(...) cerr << "[" << #__VA_ARGS__ << "]:", degug_out(__VA_ARGS__)
#else
#define degug(...) 42
#define cerr if(0)cout
#endif
#define sdb __attribute((optimize("-O3"),target("arch=sandybridge")))
ll n,shop,q,ep; vector<pi>shops;
vector<pair<int,int>>v[MAXN];
pi edges[MAXN];
ll ans[MAXN];
int depth[MAXN], p[MAXN][21]; ll dist[MAXN]; int st[MAXN], en[MAXN], co=1;
void sdb dfs(int x,int par){
	st[x]=co++;p[x][0]=par;
	for(auto i:v[x])if(i.f!=par){
		depth[i.f]=depth[x]+1; dist[i.f]=dist[x]+i.s; dfs(i.f,x);
	}
	en[x]=co;
}
bool sdb isp(int a,int b){return st[a]<=st[b]&&en[a]>=en[b];}
int sdb lca(int x,int y){
	if(isp(x,y))return x;
	if(isp(y,x))return y;
	for(int i=20;i>=0;--i){
		if(!isp(p[x][i],y))x=p[x][i];
	}
	return p[x][0];
}
void sdb t2k() { for(int j=1;j<21;++j) for(int i=1;i<=n;++i) p[i][j]=p[p[i][j-1]][j-1]; }
ll sdb disty(int x,int y){return dist[x]+dist[y]-2*dist[lca(x,y)];}
multiset<ll>vals[MAXN]; int sz[MAXN], total=0, cp[MAXN], root;
bitset<MAXN>used;
struct centD {
	void sdb dfs1(ll x,ll p){
		sz[x]=1; total++;
		for(auto i:v[x])if(i.f!=p&&!used[i.f]){ dfs1(i.f,x); sz[x]+=sz[i.f]; } 
	}
	ll sdb dfs2(ll x,ll p){
		for(auto i:v[x])if(i.f!=p&&sz[i.f]>total/2&&!used[i.f])return dfs2(i.f,x);
		return x;
	}
	void sdb main() { used=0; solve(ep,-1); }
	void sdb solve(ll x,ll p){
		total=0;
		dfs1(x,p);
		ll c=dfs2(x,p);
		if(p==-1) { root=c; cp[c]=c; }
		else { cp[c]=p; }
		x=c;
		used[x]=1;
		for(auto i:v[x])if(!used[i.f]){
// 			v[i.f].erase(pi(x,i.s));
			solve(i.f,x);
		}
		v[x].clear();
	}
	void sdb update(ll x,ll o){
		vals[x].ins(disty(x,o));
		if(cp[x]^x) update(cp[x],o);
	}
	ll sdb query(ll x,ll o){
		ll ans=(vals[x].size()?(*vals[x].begin()+disty(x,o)):LLINF);
		if(cp[x]^x) return min(ans,query(cp[x],o));
		return ans;
	}
	void sdb re(ll x,ll o){
		vals[x].erase(vals[x].find(disty(x,o)));
		if(cp[x]^x) re(cp[x],o);
	}
} cen;
vector<spi>more,moadd; ll sqn=1909;
bool sdb cmp(spi x,spi y){
	if(x.s.f/sqn==y.s.f/sqn) {
		return x.s.s<y.s.s; 
	} else return x.s.f<y.s.f;
}
void sdb funny(){
	vector<spi>mo2;
	for(auto i:more) if(i.s.f<=i.s.s) mo2.pb(i); else ans[i.f]=-5;
	more=mo2;
}
void sdb funny2(){
	vector<spi>mo2;
	for(auto i:moadd) if(i.s.f<=i.s.s) mo2.pb(i); else ans[i.f]=-5;
	moadd=mo2;
}
int QQ[MAXN];
int sdb main()
{
	FAST
	cin>>n>>shop>>q>>ep;
	FOR(i,1,n){
		int a,b,c;cin>>a>>b>>c;
		v[a].pb(pi(b,c));v[b].pb(pi(a,c));edges[i]=pi(a,b);
	}
	dfs(ep,ep);
	t2k();
	cen.main();
	FOR(i,0,shop){
		ll a;cin>>a;shops.eb(st[a],a);
	} sort(all(shops)); fill(ans,ans+q,LLINF);
	FOR(ii,0,q){
		ll i,sp;cin>>i>>sp; QQ[ii]=sp;
		ll a=edges[i].f,b=edges[i].s;
		if(depth[a]>depth[b])swap(a,b);
		//~ cerr<<a<<' '<<sp<<' '<<ep<<' '<<lca(sp,ep)<<'\n';
		if(isp(ep,a)&&isp(b,sp)){ if(shop==n) { ans[ii]=0; continue; }
			if(isp(b,sp)) { 
				//~ mo.eb(ii,pi(st[ep],st[b]-1)); 
				//~ if(en[b]<=en[ep]-1){mo.eb(ii,pi(en[b],en[ep]-1));}
				moadd.eb(ii,pi(st[b],en[b]-1));
			}
			else { more.eb(ii,pi(st[b],en[b]-1)); }
		}
		else {
			ans[ii]=-LLINF;
		}
	}
	for(auto &i:more){
		//~ cerr<<i.s.f<<' '<<i.s.s<<" became ";
		i.s.f=lbd(shops,pi(i.s.f,0))-shops.begin();
		i.s.s=ubd(shops,pi(i.s.s,LLINF))-shops.begin()-1;
		//~ cerr<<i.s.f<<' '<<i.s.s<<'\n';
	}
	funny(); 
	sort(all(more),cmp);
	for(auto i:shops) cen.update(i.s,i.s);
	for(ll i=0;i<q;++i) if(ans[i]==-5) ans[i]=cen.query(QQ[i],QQ[i]);
	ll curl=0,curr=0;
	for(ll i=0;i<(int)more.size();i++){
		ll L=more[i].s.f, R=more[i].s.s;
		ll ind=more[i].f;
		while(curr<=R){
			cen.re(shops[curr].s,shops[curr].s); curr++;
		}
		while(curr-R>=2){
			--curr; cen.update(shops[curr].s,shops[curr].s);
		}
		while(L<curl){
			--curl;cen.re(shops[curl].s,shops[curl].s);
		}
		while(L>curl){
			cen.update(shops[curl].s,shops[curl].s); ++curl;
		}
		/* answer here*/ 
		//~ cerr<<ind<<' '<<QQ[ind]<<'\n';
		ans[ind]=min(ans[ind],cen.query(QQ[ind], QQ[ind]));
	}
	//~ FOR(i,0,q) if(ans[i]==-LLINF) cout<<"escaped\n"; else if(ans[i]==LLINF) cout<<"oo\n"; else cout<<ans[i]<<'\n';
	
	
	
	for(auto &i:moadd){
		//~ cerr<<i.s.f<<' '<<i.s.s<<" became ";
		i.s.f=lbd(shops,pi(i.s.f,0))-shops.begin();
		i.s.s=ubd(shops,pi(i.s.s,LLINF))-shops.begin()-1;
		//~ cerr<<i.s.f<<' '<<i.s.s<<'\n';
	}
	funny2(); 
	sort(all(moadd),cmp); FOR(i,0,MAXN)vals[i].clear();
	//~ for(auto i:shops) cen.update(i.s,i.s);
	for(ll i=0;i<q;++i) if(ans[i]==-5) ans[i]=cen.query(QQ[i],QQ[i]);
	curl=0,curr=0;
	for(ll i=0;i<(int)moadd.size();i++){
		ll L=moadd[i].s.f, R=moadd[i].s.s;
		ll ind=moadd[i].f;
		while(curr<=R){
			cen.update(shops[curr].s,shops[curr].s); curr++;
		}
		while(curr-R>=2){
			--curr; cen.re(shops[curr].s,shops[curr].s);
		}
		while(L<curl){
			--curl;cen.update(shops[curl].s,shops[curl].s);
		}
		while(L>curl){
			cen.re(shops[curl].s,shops[curl].s); ++curl;
		}
		/* answer here*/ 
		//~ cerr<<ind<<' '<<QQ[ind]<<'\n';
		ans[ind]=min(ans[ind],cen.query(QQ[ind], QQ[ind]));
	}
	FOR(i,0,q) if(ans[i]==-LLINF) cout<<"escaped\n"; else if(ans[i]==LLINF) cout<<"oo\n"; 
	else cout<<ans[i]<<'\n';

}
/*
 * 
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5
* 
10 2 1 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
8
7
1 5
* 
5 2 1 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
*/

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