제출 #846050

#제출 시각아이디문제언어결과실행 시간메모리
846050shadow_samiValley (BOI19_valley)C++17
36 / 100
3026 ms122556 KiB
#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); 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...