Submission #1252227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252227		3m17	Valley (BOI19_valley)	C++20	100 / 100	270 ms	56840 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fi first
#define se second
#define int long long

const int Nmax = 5e5 + 174;
const int LogN = 18;

int n , q , S , E;
int u[Nmax] , v[Nmax];
int par[Nmax][18] , AnsMin[Nmax][18];
int dep[Nmax] , dp[Nmax] , dist[Nmax];
int times , inp[Nmax] , out[Nmax];
bool Shop[Nmax];

vector <pair<int , int>> graph[Nmax];

void DFS(int u)
{
    if(Shop[u]) dp[u] = dist[u];
    inp[u] = ++times;
    for (pair <int , int> v : graph[u])
    if(par[u][0] != v.first)
    {
        par[v.first][0] = u;
        dist[v.first] = dist[u] + v.second;
        dep[v.first] = dep[u] + 1;
        DFS(v.first);
        dp[u] = min(dp[v.first] , dp[u]);

        //dp[u] = min(dp[u] , dp[v.first]);
    }
    AnsMin[u][0] = dp[u] - 2 * dist[u];
    out[u] = times;
}

void Binary_Lifting()
{
    for (int i = 1 ; i <= 17 ; i++)
        for (int u = 1 ; u <= n ; u++)
        {
            par[u][i] = par[par[u][i - 1]][i - 1];
            AnsMin[u][i] = min(AnsMin[u][i - 1] , AnsMin[par[u][i - 1]][i - 1]);
        }
}

int Get (int u , int x)
{
    int Ans = 1e15;
    for (int i = 17 ; i >= 0 ; i--)
    if(x & (1 << i))
    {
        x -= (1 << i);
        Ans = min(Ans , AnsMin[u][i]);
        u = par[u][i];
    }
    return Ans;
}

main(){
    cin >> n >> S >> q >> E;
    for (int i = 1 ; i < n ; i++)
    {
        int w;
        cin >> u[i] >> v[i] >> w;
        graph[u[i]].push_back({v[i] , w});
        graph[v[i]].push_back({u[i] , w});
    }

    for (int i = 1 ; i <= n ; i++)
    {
        dp[i] = 1e15;
        //for (int v = 0 ; v < LogN ; v++) AnsMin[i][v] = 1e15;
    }

    for (int i = 1 ; i <= S ; i++)
    {
        int s;
        cin >> s;
        Shop[s] = true;
    }

    DFS(E);
    Binary_Lifting();

    //cout << AnsMin[7][0] << ' ' << AnsMin[7][1] << '\n';
    /*
    for (int i = 1 ; i <= n ; i++)
    cout << dp[i] << ' ' << AnsMin[i][0] << '\n';
    */
    for (int i = 1 ; i <= q ; i++)
    {
        int idx , R;
        cin >> idx >> R;
        int uSon = (dep[u[idx]] < dep[v[idx]] ? v[idx] : u[idx]);
        //cout << uSon << ' ';
        if(inp[uSon] <= inp[R] && out[R] <= out[uSon])
        {
            if(dp[uSon] == 1e15) cout << "oo" << '\n';
            else cout << dist[R] + Get(R , dep[R] - dep[uSon] + 1) << '\n';
        }
        else cout << "escaped" << '\n';
    }
}

Compilation message (stderr)

valley.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main(){
      | ^~~~

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