Submission #694723

#TimeUsernameProblemLanguageResultExecution timeMemory
694723KiaRezValley (BOI19_valley)C++17
23 / 100
280 ms56104 KiB
/* 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; // 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]; pii Ed[_N]; void getEdge() { int 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=1e18) { dist[v][0]=EW, par[v][0]=p, tin[v]=++t; dp[v][_lg] = (Shop[v] ? 0 : 1e18); FOR(i,1,_lg-1) { par[v][i]=par[par[v][i-1]][i-1], dist[v][i]=dist[v][i-1]+dist[par[v][i-1]][i-1]; } 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) { 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; } int main () { ios; cin>>n>>S>>Q>>E; 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]=1e18;} dfs(); 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]; FORD(i,_lg-1,0) { if(h[par[R][i]]>=h[root] && par[R][i]!=0) { ans=min(dp[R][i], ans);R=par[R][i]; } } if(ans==1e18) {cout<<"oo\n";} else {cout<<ans<<endl;} } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...