Submission #694819

#	Time	Username	Problem	Language	Result	Execution time	Memory
694819		KiaRez	Valley (BOI19_valley)	C++17	100 / 100	252 ms	61144 KiB

valley

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define SQ									   350
#define endl                                   '\n'
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define PQ                                     priority_queue
#define size(x)                                ((ll)x.size())
#define DASH                                   "---------"
#define UNDERLINE                              "_________"
#define all(x)                                 (x).begin(),(x).end()
#define FORD(i, s, e)                          for(int i=s; i>=e; --i)
#define FOR(i, s, e)                           for(int i=s; i<=e; ++i)
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int _N = 232323, _LG=131072, _lg=18;
const ll _MOD = 1e9+7, INF=1e18; // 998244353

ll getmod(ll a, ll mod=_MOD)                   {return (a+3*mod)%mod;}
ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}

int n, S, Q, E, tin[_N], tout[_N], t, Shop[_N], ind, par[_N][_lg+1], I, R, h[_N];
ll dp[_N][_lg+1], dist[_N][_lg+1];
vector<pll> adj[_N];
pll Ed[_N];

void getEdge() {
	ll v,u,w;
	cin>>v>>u>>w;
	adj[v].pb({u, w});
	adj[u].pb({v, w});
	Ed[++ind]={v,u};
}

void dfs(int v=E, int p=0, ll EW=INF) {
	dist[v][0]=EW, par[v][0]=p, tin[v]=++t;
	dp[v][_lg] = (Shop[v] ? 0 : INF);
	FOR(i,1,_lg-1) {
		par[v][i]=par[par[v][i-1]][i-1], dist[v][i]=min(dist[v][i-1]+dist[par[v][i-1]][i-1], INF);
	}
	for(auto it : adj[v]) {
		if(it.F!=p) {
			h[it.F]=h[v]+1;
			dfs(it.F, v, it.S);
			dp[v][_lg] = min(dp[v][_lg], dp[it.F][_lg]+it.S);
		}
	}
	tout[v]=++t;
}

void dsf(int v=E, int p=0, ll EW=INF) {
	dp[v][0] = min(dp[v][_lg], EW+dp[p][_lg]);
	FOR(i,1,_lg-1) {
		dp[v][i] = min(dp[v][i-1], dist[v][i-1] + dp[par[v][i-1]][i-1]);
	}
	for(auto it : adj[v]) {
		if(it.F!=p) {dsf(it.F, v, it.S);}
	}
}

int main () {
	ios;

	cin>>n>>S>>Q>>E; h[E]=1;
	FOR(i,1,n-1) {getEdge();}
	FOR(i,1,S) {int C;cin>>C;Shop[C]=1;}
	FOR(i,0,_lg) {dp[0][i]=dist[0][i]=INF;}
	dfs();
	dsf();
	FOR(q,1,Q) {
		cin>>I>>R;
		if(!(tin[Ed[I].F]<=tin[R] && tout[Ed[I].F]>=tout[R] && tin[Ed[I].S]<=tin[R] && tout[Ed[I].S]>=tout[R])) {
			cout<<"escaped\n"; continue;
		}
		int root=(h[Ed[I].F] > h[Ed[I].S] ? Ed[I].F : Ed[I].S);
		ll ans=dp[R][_lg], tmp=0;
		FORD(i,_lg-1,0) {
			if(h[par[R][i]]>=h[root] && par[R][i]!=0 && tmp<INF) {
				ans=min(min(dp[R][i], dp[R][_lg])+tmp, ans);tmp+=dist[R][i];R=par[R][i];
			}
		}
		if(ans>=INF || ans<0) {cout<<"oo\n";}
		else {cout<<ans<<endl;}
	}

	return 0;
}

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