Submission #912552

#	Time	Username	Problem	Language	Result	Execution time	Memory
912552		asdasdqwer	Valley (BOI19_valley)	C++14	100 / 100	458 ms	82436 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii array<int,2>
#define tii array<int,3>

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,s,q,e;cin>>n>>s>>q>>e;
    e--;

    vector<vector<pii>> g(n);
    vector<tii> edg;
    for (int i=1;i<n;i++) {
        int a,b,w;cin>>a>>b>>w;
        a--;b--;
        g[a].push_back({b,w});
        g[b].push_back({a,w});
        edg.push_back({a,b,w});
    }

    vector<bool> shop(n,false);
    for (int i=0;i<s;i++) {
        int c;cin>>c;shop[--c]=true;
    }

    vector<int> dp(n,1e16);
    vector<vector<int>> lft(n, vector<int>(20,-1)), weight(n, vector<int>(20,0)), shr(n, vector<int>(20,1e16));
    vector<int> d(n,0);
    function<void(int,int)> dfs=[&](int node, int pv) {
        if (shop[node]) {
            dp[node]=0;
        }

        for (auto [x, w]:g[node]) {
            if (x==pv)continue;
            d[x]=d[node]+1;
            lft[x][0]=node;
            weight[x][0]=w;
            dfs(x,node);
            dp[node]=min(dp[node],dp[x]+w);
        }
    };

    dfs(e,-1);

    for (int i=0;i<n;i++) {
        if (e == i) continue;
        shr[i][0] = dp[lft[i][0]] + weight[i][0];
    }

    for (int j=1;j<20;j++) {
        for (int i=0;i<n;i++) {
            lft[i][j]=lft[i][j-1];
            if (lft[i][j]!=-1) {
                lft[i][j]=lft[lft[i][j]][j-1];
                weight[i][j]=weight[i][j-1]+weight[lft[i][j-1]][j-1];
                shr[i][j] = min(shr[i][j-1], shr[lft[i][j-1]][j-1] + weight[i][j-1]);
            }
        }
    }

    function<int(int,int)> jmp=[&](int a,int steps)->int {
        int cnt=0;
        while (steps) {
            if ((steps&1)==1) {
                a=lft[a][cnt];
                if (a==-1)return-1;
            }
            cnt++;steps>>=1;
        }
        return a;
    };

    function<int(int,int)> lca=[&](int a,int b) -> int {
        if (d[a]<d[b])swap(a,b);
        a=jmp(a,d[a]-d[b]);
        if(a==b)return a;

        for (int i=19;i>=0;i--) {
            if(lft[a][i]!=lft[b][i]) {
                a=lft[a][i];
                b=lft[b][i];
            }
        }
        return lft[a][0];
    };

    function<int(int,int)> shortest=[&](int a, int steps) -> int {
        int mn = dp[a];
        int pWeight=0;
        int cnt=0;

        while (steps) {
            if ((steps&1)==1) {
                int candidate = pWeight + shr[a][cnt];
                mn = min(mn, candidate);
                pWeight += weight[a][cnt];
                a=lft[a][cnt];
            }
            steps>>=1;cnt++;
        }
        return mn;
    };

    while (q--) {
        int i,r;cin>>i>>r;
        i--;r--;
        int n1=edg[i][0], n2=edg[i][1];
        if (d[n1] <= d[r] && d[n2] <= d[r] && lca(n1, r) == n1 && lca(n2, r) == n2) {
            int low=max(d[n1], d[n2]);
            int mn = shortest(r, d[r]-low);
            if (mn >= 1e16) {
                cout<<"oo\n";
            }

            else {
                cout<<mn<<"\n";
            }
        }

        else {
            cout<<"escaped\n";
        }
    }
}

Compilation message (stderr)

valley.cpp: In lambda function:
valley.cpp:38:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for (auto [x, w]:g[node]) {
      |                   ^

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