Submission #834562

#	Time	Username	Problem	Language	Result	Execution time	Memory
834562		BT21tata	Valley (BOI19_valley)	C++17	100 / 100	211 ms	40012 KiB

valley

#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define SPEED ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define rall(v) (v).rbegin(),(v).rend()
#define all(v) (v).begin(),(v).end()
#define setp fixed<<setprecision
#define OK cerr<<"OK"<<endl<<flush
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define F first
#define S second
#define y0 jahdakdh
#define y1 jahsadakdakdh
#define endl '\n'
const ll MOD=1e9+7;
const ll mod=(1ll<<31)-1;
const ld eps=1e-8;
const ll MAXLONG=9223372036854775807;
const ll MINLONG=-9223372036854775807;
using namespace std;
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
const int N=1e5+5;

struct edge
{
    int p, u, w;
}e[N];

int n, s, q, root, par[N], tin[N], tout[N], tmr, up[N][18];
ll de[N], val[N], valup[N][18];
vector<pii>g[N];
bitset<N>shop;

void dfs(int v, int p)
{
    tin[v]=++tmr;
    par[v]=p;
    if(!shop[v]) val[v]=MOD*MOD;
    for(pii u : g[v])
    {
        if(u.F==p) continue;
        de[u.F]=de[v]+u.S;
        dfs(u.F, v);
        if(val[u.F]!=MOD*MOD) val[v]=min(val[v], val[u.F]+u.S);
    }
    tout[v]=++tmr;
}

void calcup(int v, int p)
{
    up[v][0]=p;
    valup[v][0]=val[p];

    for(int i=1; i<18; i++)
    {
        up[v][i]=up[up[v][i-1]][i-1];
        valup[v][i]=min(valup[v][i-1], valup[up[v][i-1]][i-1]);
    }

    for(pii u : g[v])
        if(u.F!=p) calcup(u.F, v);
}

inline bool anc(int v, int u)
{
    return (tin[v]<=tin[u] and tout[u]<=tout[v]);
}

ll goup(int v, int p)
{
    ll ret=MOD*MOD;
    for(int i=17; i>=0; i--)
    {
        if(anc(p, up[v][i]))
        {
            ret=min(ret, valup[v][i]);
            v=up[v][i];
        }
    }
    return ret;
}

int main()
{
    SPEED;
    cin>>n>>s>>q>>root;
    for(int i=1; i<n; i++)
    {
        cin>>e[i].p>>e[i].u>>e[i].w;
        g[e[i].p].pb({e[i].u, e[i].w});
        g[e[i].u].pb({e[i].p, e[i].w});
    }
    for(int i=0; i<s; i++)
    {
        int x; cin>>x;
        shop[x]=1;
    }
    dfs(root, 0);
    
    for(int i=1; i<=n; i++)
    {
        //cout<<"val = "<<i<<' '<<val[i]<<endl;
        if(val[i]!=MOD*MOD) val[i]-=de[i];
        //cout<<"val last = "<<i<<' '<<val[i]<<endl;
    }
    for(int i=1; i<n; i++)
        if(par[e[i].p]==e[i].u) swap(e[i].u, e[i].p);

    val[0]=MOD*MOD;
    memset(valup, 63, sizeof(valup));
    calcup(root, 0);
    while(q--)
    {
        int idx, v;
        cin>>idx>>v;
        if(!anc(e[idx].u, v))
        {
            cout<<"escaped\n";
            continue;
        }
        else
        {
            if(val[e[idx].u]==MOD*MOD)
            {
                cout<<"oo\n";
                continue;
            }
            cout<<min(val[v]+de[v], goup(v, e[idx].u)+de[v])<<endl;
        }
    }
    return 0;
}

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