Submission #1133276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133276		friedel	Valley (BOI19_valley)	C++20	100 / 100	217 ms	49280 KiB

valley

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using llu=unsigned long long;
using ll=long long;
using ld=long double;
using pir=pair<ll,ll>;
using vl=vector<ll>;
using sl=set<ll>;
using msl=multiset<ll>;
using prq=priority_queue<ll>;
using prqi=priority_queue<ll,vector<ll>,greater<ll>>;
using ma=map<ll,ll>;
using vp=vector<pair<ll,ll>>;
using vvl=vector<vector<ll>>;
using vvp=vector<vector<pair<ll,ll>>>;
using sp=set<pair<ll,ll>>;
using msp=multiset<pair<ll,ll>>;
#define nfs string::npos
#define count1(n) __builtin_popcountll(n)
#define last1(n) __builtin_ctzll(n)
#define first1(n) 63-__builtin_clzll(n)
#define maxi(v) max_element(all(v))
#define mini(v) min_element(all(v))
#define lb(n) lower_bound(n)
#define ub(n) upper_bound(n)
#define lbd(v,n) lower_bound(all(v),n)
#define ubd(v,n) upper_bound(all(v),n)
#define bins(v,n) binary_search(all(v),n)
#define fr(i,a,b) for(i=a;i<=b;i++)
#define fv(i,a,b) for(i=a;i>=b;i--)
#define f(i,n) for(i=0;i<n;i++)
#define fn(i,n) for(i=n-1;i>=0;i--)
#define pb push_back
#define ppb pop_back
#define all(v) v.begin(),v.end()
#define g(v,n) vl v(n); f(_,n) cin>>v[_]
#define bs(n,x) bitset<n> (x).to_string()
#define invp(v,n) vp v;f(_,n) cin>>v[_].first>>v[_].second
#define seev(v) for(auto ggg:v) cout<<ggg<<"-"
#define print(v) for(auto ggg:v) cout<<ggg<<" "
const ll inf=4e18;
const ll mod=1000000007;
const ll mod2=998244353;

ll power(ll a,ll b,ll p=inf)
{
    ll res=1;a%=p;
    while(b>0)
    {
        if(b%2==1)
            res=(res*a)%p;
        a=(a*a)%p;
        b=b/2;
    }
    return res;
}
ll log(ll n,ll k)
{
    ll a=k,b=0;
    while(a<=n)
        a*=k,b++;
    return b;
}
ll todec(ll n,string s)
{
    ll i,k=0;
    f(i,n)
        if(s[i]=='1')
            k+=1LL<<(n-i-1);
    return k;
}
bool vps(const pair<ll,ll> &a,const pair<ll,ll> &b)
{
    return (a.second<b.second);
}
bool fts(const pair<ll,ll> &a,const pair<ll,ll> &b)
{
    if(a.first!=b.first)
        return (a.first<b.first);
    return (a.second>b.second);
}
vl segtree(vl& v)
{
    ll i,n=v.size();
    ll p=power(2,log(n-1,2)+1);
    f(i,p-n)
        v.pb(0);
    n=v.size();
    vl sgt(2*n);
    fr(i,n,2*n-1)
        sgt[i]=v[i-n];
    fn(i,n)
        sgt[i]=max(sgt[2*i],sgt[2*i+1]);
    return sgt;
}
void update(vl& sgt,ll k,ll x)
{
    ll n=sgt.size()/2;k+=n;
    sgt[k]=x;
    for(k=k/2;k>0;k/=2)
        sgt[k]=max(sgt[2*k],sgt[2*k+1]);
}
ll query(vl& sgt,ll l,ll r)
{
    ll n=sgt.size()/2,q=-inf;
    l+=n;r+=n;
    while(l<=r)
    {
        if(l%2==1)
            q=max(q,sgt[l++]);
        if(r%2==0)
            q=max(q,sgt[r--]);
        l/=2;r/=2;
    }
    return q;
}

vl level(vvp& v,ll root)
{
    ll n=v.size()-1;
    vl lvl(n+1),vt(n+1);
    function<void(ll)> dfs=[&](ll nd)
    {
        vt[nd]=1;
        for(auto g:v[nd])
        {
            if(vt[g.first])
                continue;
            lvl[g.first]=lvl[nd]+1;
            dfs(g.first);
        }
    };
    dfs(root);
    return lvl;
}
pir merge(pir a,pir b)
{
    vl v={a.first,a.second,b.first,b.second};
    sort(all(v));
    return {v[0],v[1]};
}
vvl binup(vvp& v,ll root,vvl& data,vl& ht,vl& lvl)
{
    ll i,j,n=v.size()-1;
    ll m=first1(n)+1;
    vvl bin(m,vl(n+1));
    data.resize(m,vl(n+1,inf));
    vl vt(n+1);
    function<void(ll)> dfs=[&](ll nd)
    {
        vt[nd]=1;
        for(auto g:v[nd])
        {
            if(vt[g.first])
                continue;
            bin[0][g.first]=nd;
            dfs(g.first);
        }
    };
    dfs(root);
    fr(j,1,m-1)
        fr(i,1,n)
            bin[j][i]=bin[j-1][bin[j-1][i]];

    vp info(n+1,{inf,inf});
    fr(i,1,n)
    {
        info[i]={ht[i]-lvl[i],inf};
        for(auto g:v[i])
            if(bin[0][g.first]==i)
                info[i]=merge(info[i],{ht[g.first]-lvl[g.first]+2*g.second,inf});
    }

    fr(i,1,n)
    {
        data[0][i]=info[bin[0][i]].first;
        ll x=0;
        for(auto g:v[bin[0][i]])
            if(g.first==i)
                x=g.second;
        if(info[bin[0][i]].first==ht[i]-lvl[i]+2*x)
            data[0][i]=info[bin[0][i]].second;
    }
    fr(j,1,m-1)
        fr(i,1,n)
            data[j][i]=min(data[j-1][i],data[j-1][bin[j-1][i]]);

    return bin;
}
ll lca(vvl& bin,vl& lvl,ll a,ll b)
{
    ll i,lc,m=bin.size();
    if(lvl[a]<lvl[b])
        swap(a,b);
    fn(i,m)
        if(lvl[a]-(1ll<<i)>=lvl[b])
            a=bin[i][a];
    if(a==b)
        return a;
    fn(i,m)
        if(bin[i][a]!=bin[i][b])
            a=bin[i][a],b=bin[i][b];
    return bin[0][a];
}
void solve(ll tc)
{
    ll n,m,k=0,j=0,i=0,x=0,y=0,z=0,p=0,q=0,l=0,sum=0,temp=1,flag=0,a=0,b=0,c=0,d=1,r=0,mn=inf,mx=-inf,_,__,mid;
    string s1,s2,s3,s;char ch;
    cin>>n>>m>>q>>p;
    vvp v(n+1);
    vp edge(n);
    f(i,n-1)
    {
        cin>>x>>y>>d;
        edge[i+1]={x,y};
        v[x].pb({y,d});
        v[y].pb({x,d});
    }
    vl vt(n+1),ht(n+1,inf),lvl(n+1);
    f(i,m)
    {
        cin>>x;ht[x]=0;
    }
    vl tin(n+1),tout(n+1);c=0;
    function<void(ll)>dfs=[&](ll nd)
    {
        vt[nd]=1;
        tin[nd]=++c;
        for(auto g:v[nd])
        {
            if(vt[g.first])
                continue;
            lvl[g.first]=lvl[nd]+g.second;
            dfs(g.first);
            ht[nd]=min(ht[nd],ht[g.first]+g.second);
        }
        tout[nd]=c;
    };
    dfs(p);
    ht[0]=inf;
    vvl data;
    vvl bin=binup(v,p,data,ht,lvl);
    vl lvvl=level(v,p);
    while(q--)
    {
        cin>>p>>x;c=x;
        x=edge[p].first;
        y=edge[p].second;
        if(tin[y]>tin[x])
            swap(x,y);
        if(!(tin[c]>=tin[x]&&tin[c]<=tout[x]))
        {
            cout<<"escaped"<<endl;
            continue;
        }

        k=lvvl[c]-lvvl[x];x=c;
        mn=ht[x]-lvl[x];
        s=bs(20,k);
        reverse(all(s));
        f(i,20)
        {
            if(s[i]=='1')
            {
                mn=min(mn,data[i][x]);
                x=bin[i][x];
            }
        }
        if(mn+lvl[c]==inf)
            cout<<"oo"<<endl;
        else
            cout<<mn+lvl[c]<<endl;
    }
}

//Use variables correctly
//Check for boundary conditions
//Write the step statement in while loops
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    ll t=1;
//    cin>>t;
    while(t--)
    {
        solve(t);
        cout<<endl;
    }
    return 0;
}

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