Submission #609070

#	Time	Username	Problem	Language	Result	Execution time	Memory
609070		mayureshpatle	Valley (BOI19_valley)	C++17	100 / 100	257 ms	50024 KiB

valley

/**************************************************************
Submitted By: Mayuresh N. Patle
Written On: Wednesday, July 27, 2022
**************************************************************/

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mod1 998244353
#define rep(i,s,e) for(i=s;i<e;++i)
#define repr(i,s,e) for(i=s;i>e;--i)
#define fp(i) fixed<<setprecision(i)
#define in(a) for(auto &ghe:a) cin>>ghe;
#define in2d(a) for(auto &ghe:a) for(auto &he:ghe) cin>>he;
#define out(a) for(auto &ghe:a) cout<<ghe<<" ";cout<<endl;
#define out2d(a) {for(auto &he:a) {out(he)}}
#define loop(i,a) for(auto &i:a)
#define inrange(i,j,k) (((i)<=(j)) && ((j)<(k)))
#define make(a,i) memset(a,i,sizeof(a))
#define chk(x) cerr<<(#x)<<":"<<(x)<<endl;
#define chk2(x,y) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<endl;
#define chk3(x,y,z) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector <ll> vll;
typedef vector <float> vf;
typedef vector <ld> vld;
#define pb push_back
#define pob() pop_back()
typedef pair <ll,ll> pll;
#define F first
#define S second
#define mp(a,b) make_pair(a,b)
typedef vector <pll> vp;
typedef vector <bool> flags;
#define all(v) begin(v),end(v)
#define amin(var, val) var = (val)<var ? (val) : var
#define amax(var, val) var = (val)>var ? (val) : var

class edge
{
    public:
    ll u,v,w;
    edge (){}
    edge (ll u, ll v, ll w): u(u), v(v), w(w){}
    ll op(ll x) {return x^u^v;}
};

const ll N=1e5+1, h=18, oo=1e18;
vll G[N];
vector <edge> e;

ll up[N][h], dp[N][h], val[N];
ll dist[N], tin[N], tout[N], _t=0;

ll sd[N], s[N];

void dfs(ll v, ll p)
{
    tin[v] = ++_t;

    up[v][0] = p;
    dist[v] += dist[p];

    sd[v] = oo;
    if(s[v]) sd[v] = dist[v];

    loop(i, G[v])
    {
        ll u=e[i].op(v), w=e[i].w;
        if(u==p) continue;
        dist[u] = w;     
        dfs(u,v);
        e[i].v = u;
        e[i].u = v;
        amin(sd[v], sd[u]);
    }

    dp[v][0] = oo;
    if(sd[v]!=oo) dp[v][0] = sd[v] - 2ll*dist[v];
    val[v] = dp[v][0];

    tout[v] = ++_t;
}

bool is_anc(ll p, ll v)
{
    return tin[p]<=tin[v] and tout[p]>=tout[v];
}

ll get(ll v,ll p)
{
    ll i, ans=val[p];
    repr(i,h-1,-1)
    {
        if(is_anc(p, up[v][i])) amin(ans, dp[v][i]), v=up[v][i];
    }

    return ans;
}


void preprocess()
{
    
    return;
}

void solve()
{
    ll n,m,q,r,i;

    cin>>n>>m>>q>>r;
    rep(i,1,n)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        G[u].pb(e.size());
        G[v].pb(e.size());
        e.pb(edge(u,v,w));
    }

    while(m--) cin>>i, s[i]=1;

    loop(v, dp) loop(i, v) i=oo;

    dfs(r, 0);

    rep(i,1,h) rep(r,1,n+1) 
    {
        dp[r][i] = min(dp[r][i-1], dp[up[r][i-1]][i-1]);
        up[r][i] = up[up[r][i-1]][i-1];
    }

    while(q--)
    {
        cin>>i>>r;
        --i;
        ll v = e[i].v;
        if(!is_anc(v, r)) cout<<"escaped\n";
        else
        {
            ll ans = get(r, v);
            if(ans==oo) cout<<"oo\n";
            else cout<<ans+dist[r]<<"\n";
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T=1,i;
    //cin>>T;
    preprocess();
    rep(i,0,T)
    {
        //cout<<"Case #"<<i+1<<": ";
        solve();
    }
    return 0;
}

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