Submission #493646

#	Time	Username	Problem	Language	Result	Execution time	Memory
493646		Fysty	Valley (BOI19_valley)	C++14	100 / 100	237 ms	50628 KiB

valley

#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;
const ld PI=3.14159265358979323846;
ll gcd(ll a,ll b){if(b==0) return a; return gcd(b,a%b);}
ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll ans=fpow(a*a%m,b/2,m);
    return (b%2?ans*a%m:ans);
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
//#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repk(i,m,n) for(int i=m;i<n;i++)
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)
const int N=1e5+1;
ll dep[N],dist[N],tmp[N],in[N],out[N],an[18][N],mn[18][N],t=0;
bool is[N];
vector<pll> ed[N];
void dfs(ll n,ll p)
{
    in[n]=t++;
    dep[n]=(p==0?0:dep[p]+1);
    if(is[n]) tmp[n]=dist[n];
    for(pll u:ed[n])
    {
        if(u.F==p) continue;
        dist[u.F]=dist[n]+u.S;
        dfs(u.F,n);
        an[0][u.F]=n;
        tmp[n]=min(tmp[n],tmp[u.F]);
    }
    out[n]=t++;
}
bool isan(ll u,ll v){return (in[u]<=in[v]&&out[v]<=out[u]);}
signed main()
{
    MottoHayaku
    ll n,s,q,a;
    cin>>n>>s>>q>>a;
    vector<pll> e;
    rep1(i,n) tmp[i]=INF;
    rep(i,n-1)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        e.pb({u,v});
        ed[u].pb({v,w});
        ed[v].pb({u,w});
    }
    rep(i,s)
    {
        ll c;
        cin>>c;
        is[c]=1;
    }
    an[0][a]=a;
    dfs(a,0);
    rep1(i,n) mn[0][i]=min(tmp[i]-dist[i]*2,tmp[an[0][i]]-dist[an[0][i]]*2);
    rep1(i,17)
    {
        rep1(j,n)
        {
            an[i][j]=an[i-1][an[i-1][j]];
            mn[i][j]=min(mn[i-1][j],mn[i-1][an[i-1][j]]);
        }
    }
    while(q--)
    {
        ll id,x;
        cin>>id>>x;
        id--;
        pll p=e[id];
        if(dep[p.F]<dep[p.S]) swap(p.F,p.S);
        if(!isan(p.F,x)) cout<<"escaped\n";
        else
        {
            if(tmp[p.F]==INF)
            {
                cout<<"oo\n";
                continue;
            }
            if(p.F==x)
            {
                cout<<tmp[x]-dist[x]<<"\n";
                continue;
            }
            ll k=dist[x],cur=INF;
            for(int i=17;i>=0;i--)
            {
                if(isan(an[i][x],p.F)) continue;
                cur=min(cur,mn[i][x]);
                x=an[i][x];
            }
            cur=min(cur,mn[0][x]);
            cout<<k+cur<<"\n";
        }
    }
}

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