oj.uz

답안 #257755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257755 2020-08-04T17:31:42 Z Evirir Valley (BOI19_valley) C++17
100 / 100
 445 ms 39144 KB 
#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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5504 KB Output is correct
2 Correct 6 ms 5504 KB Output is correct
3 Correct 7 ms 5504 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5504 KB Output is correct
2 Correct 6 ms 5504 KB Output is correct
3 Correct 7 ms 5504 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 6 ms 5248 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 6 ms 5376 KB Output is correct
8 Correct 6 ms 5256 KB Output is correct
9 Correct 8 ms 5376 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 5 ms 5248 KB Output is correct
12 Correct 5 ms 5248 KB Output is correct
13 Correct 6 ms 5376 KB Output is correct
14 Correct 5 ms 5376 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 390 ms 30824 KB Output is correct
2 Correct 410 ms 30568 KB Output is correct
3 Correct 421 ms 30568 KB Output is correct
4 Correct 445 ms 34152 KB Output is correct
5 Correct 424 ms 34280 KB Output is correct
6 Correct 424 ms 38888 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5504 KB Output is correct
2 Correct 6 ms 5504 KB Output is correct
3 Correct 7 ms 5504 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 6 ms 5248 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 6 ms 5376 KB Output is correct
8 Correct 6 ms 5256 KB Output is correct
9 Correct 8 ms 5376 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 5 ms 5248 KB Output is correct
12 Correct 5 ms 5248 KB Output is correct
13 Correct 6 ms 5376 KB Output is correct
14 Correct 5 ms 5376 KB Output is correct
15 Correct 390 ms 30824 KB Output is correct
16 Correct 410 ms 30568 KB Output is correct
17 Correct 421 ms 30568 KB Output is correct
18 Correct 445 ms 34152 KB Output is correct
19 Correct 424 ms 34280 KB Output is correct
20 Correct 424 ms 38888 KB Output is correct
21 Correct 371 ms 29544 KB Output is correct
22 Correct 396 ms 29148 KB Output is correct
23 Correct 409 ms 29288 KB Output is correct
24 Correct 391 ms 33384 KB Output is correct
25 Correct 399 ms 39144 KB Output is correct
26 Correct 376 ms 29420 KB Output is correct
27 Correct 378 ms 29164 KB Output is correct
28 Correct 373 ms 29160 KB Output is correct
29 Correct 390 ms 31976 KB Output is correct
30 Correct 426 ms 35312 KB Output is correct
31 Correct 354 ms 29544 KB Output is correct
32 Correct 372 ms 29416 KB Output is correct
33 Correct 375 ms 29416 KB Output is correct
34 Correct 408 ms 33128 KB Output is correct
35 Correct 392 ms 39016 KB Output is correct
36 Correct 404 ms 33512 KB Output is correct