제출 #846054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
846054		shadow_sami	Valley (BOI19_valley)	C++17	100 / 100	279 ms	143576 KiB

valley

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
ll q;ll sr,de;
vector<pi> adj[mx];
ll dis[mx];
ll dep[mx];
bool mark[mx];
ll val[mx];
vector<pi> lis[mx];
vector<pi> qu[mx];
ll na[mx];
ll dp[mx];
set<ll> st[mx];
ll up[mx][20];
ll pt[mx][20];

void dfs(ll u,ll par){
	fjp(1,20)
		up[u][j] = up[up[u][j-1]][j-1];
	st[u].clear();
	st[u].insert(u);
	fx(adj[u])
		if(x.ff!=par){
			up[x.ff][0] = u;
			dep[x.ff] = dep[u] + 1;
			dis[x.ff] = dis[u] + val[x.ss];
			for( auto y : lis[x.ss])
				qu[x.ff].push_back(y);
			dfs(x.ff,u);			
			tp2 = u;
			if(st[tp2].size() < st[x.ff].size()){
				for(auto y : (st[tp2]))
					st[x.ff].insert(y);
				st[tp2].clear();
				st[tp2].swap(st[x.ff]);
			}
			else{
				for(auto y : (st[x.ff]))
					st[tp2].insert(y);
				st[x.ff].clear();
			}
		}
	if(mark[u])
		dp[u] = dis[u];
	else
		dp[u] = 1e18;
	// debug(u);
	// debug(st[u]);
	fx(adj[u])
		if(x.ff!=par){
			dp[u] = min(dp[u],dp[x.ff]);
		}
	fx(qu[u]){
		if(st[u].find(x.ff)==st[u].end()){
			na[x.ss] = -1;
			// debug(x);
		}
	}

	return;
}

void dfs2(ll u,ll par){
	pt[u][0] = dp[par];
	fjp(1,20)
		pt[u][j] = min(pt[u][j-1],pt[up[u][j-1]][j-1]);
	fx(adj[u])
		if(x.ff!=par){
			dfs2(x.ff,u);			
		}

	fx(qu[u]){
		if(na[x.ss]==-1)
			continue;
		tptp = dep[x.ff] - dep[u];
		res = 1e18;
		// debug(x);
		res = min(res,dp[x.ff]);
		tp2 = x.ff;
		fjp(0,20)
			if(tptp & (1<<j)){
				res = min(res,pt[x.ff][j]);
				x.ff = up[x.ff][j];
			}
		ans = dis[tp2] + res;
		na[x.ss] = ans;
	}
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n>>m>>q>>tp;
        fip(0,n-1){
        	cin>>sr>>de>>tp2;
        	val[i+1] = tp2;
        	adj[sr].push_back({de,i+1});
        	adj[de].push_back({sr,i+1});
        }
        fip(0,m){
        	cin>>tp2;
        	mark[tp2] = 1;
        }        
        fip(0,q){
        	cin>>sr>>de;      
        	lis[sr].push_back({de,i});
        }
        
        dep[tp] = dis[tp] = 0;
        up[tp][0] = tp;
        dfs(tp,-1);
        // fip(1,n+1){
        // 	debug(qu[i]);
        // }        	
        fip(1,n+1)
        	dp[i] -= (2*dis[i]);
        dfs2(tp,-1);
        fip(0,q){
        	if(na[i]==-1)
        		cout<<"escaped"<<nli;
        	else if(na[i]>1e15)
        		cout<<"oo"<<nli;
        	else
        		cout<<na[i]<<nli;
        }
        
    cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
} 

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