oj.uz

답안 #155341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
155341 2019-09-27T14:50:16 Z ryansee Valley (BOI19_valley) C++14
100 / 100
 1435 ms 105420 KB 
#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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 7928 KB Output is correct
2 Correct 15 ms 7800 KB Output is correct
3 Correct 18 ms 7800 KB Output is correct
4 Correct 14 ms 7800 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 7928 KB Output is correct
2 Correct 15 ms 7800 KB Output is correct
3 Correct 18 ms 7800 KB Output is correct
4 Correct 14 ms 7800 KB Output is correct
5 Correct 10 ms 7720 KB Output is correct
6 Correct 12 ms 7672 KB Output is correct
7 Correct 12 ms 7672 KB Output is correct
8 Correct 13 ms 7644 KB Output is correct
9 Correct 13 ms 7672 KB Output is correct
10 Correct 12 ms 7672 KB Output is correct
11 Correct 11 ms 7800 KB Output is correct
12 Correct 12 ms 7928 KB Output is correct
13 Correct 13 ms 8016 KB Output is correct
14 Correct 11 ms 7800 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 54968 KB Output is correct
2 Correct 677 ms 73060 KB Output is correct
3 Correct 799 ms 85476 KB Output is correct
4 Correct 958 ms 98284 KB Output is correct
5 Correct 960 ms 98660 KB Output is correct
6 Correct 1076 ms 105420 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 7928 KB Output is correct
2 Correct 15 ms 7800 KB Output is correct
3 Correct 18 ms 7800 KB Output is correct
4 Correct 14 ms 7800 KB Output is correct
5 Correct 10 ms 7720 KB Output is correct
6 Correct 12 ms 7672 KB Output is correct
7 Correct 12 ms 7672 KB Output is correct
8 Correct 13 ms 7644 KB Output is correct
9 Correct 13 ms 7672 KB Output is correct
10 Correct 12 ms 7672 KB Output is correct
11 Correct 11 ms 7800 KB Output is correct
12 Correct 12 ms 7928 KB Output is correct
13 Correct 13 ms 8016 KB Output is correct
14 Correct 11 ms 7800 KB Output is correct
15 Correct 435 ms 54968 KB Output is correct
16 Correct 677 ms 73060 KB Output is correct
17 Correct 799 ms 85476 KB Output is correct
18 Correct 958 ms 98284 KB Output is correct
19 Correct 960 ms 98660 KB Output is correct
20 Correct 1076 ms 105420 KB Output is correct
21 Correct 208 ms 29764 KB Output is correct
22 Correct 226 ms 29528 KB Output is correct
23 Correct 244 ms 29300 KB Output is correct
24 Correct 273 ms 30524 KB Output is correct
25 Correct 299 ms 31844 KB Output is correct
26 Correct 175 ms 29836 KB Output is correct
27 Correct 249 ms 29572 KB Output is correct
28 Correct 253 ms 29592 KB Output is correct
29 Correct 369 ms 30368 KB Output is correct
30 Correct 385 ms 31492 KB Output is correct
31 Correct 245 ms 32368 KB Output is correct
32 Correct 513 ms 34276 KB Output is correct
33 Correct 1292 ms 35340 KB Output is correct
34 Correct 1435 ms 37348 KB Output is correct
35 Correct 566 ms 39044 KB Output is correct
36 Correct 1117 ms 49336 KB Output is correct