Submission #1327420

#TimeUsernameProblemLanguageResultExecution timeMemory
1327420dianaValley (BOI19_valley)C++20
0 / 100
108 ms50832 KiB
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define ll long long
#define LSO(o) ((o) & -(o))
using namespace std;
int n, s, q, e, bc;
const int N = 1e5+5, C = 35;
const ll M = 1e17;
bool sh[N];
pii cel[N];
vector<pii> graf[N];
ll tcul[N], sdp[N][C];
int par[N][C];

int tme = 0, tin[N], tout[N];
void et(int v, int p)
{
    tin[v] = ++tme;
    for(auto x: graf[v])
        if(x.fi != p) et(x.fi, v);
    tout[v] = ++tme;
}

ll dfsul(int v, int p)
{
    if(sh[v]) tcul[v] = 0;
    for(auto x: graf[v])
        if(x.fi != p)
            tcul[v] = min(tcul[v], dfsul(x.fi, v)+x.se);
    return tcul[v];
}

void dfs(int v, int p, int d)
{
    par[v][0] = p;
    sdp[v][0] = d;
    for(int k=1; k<C; k++)
        par[v][k] = par[par[v][k-1]][k-1],
        sdp[v][k] = sdp[v][k-1] + sdp[par[v][k-1]][k-1];
    for(auto x: graf[v])
        if(x.fi != p)
            dfs(x.fi, v, x.se);
}

ll bm(int v, int u)
{
    int l = 0, r = n;
    while(l < r)
    {
        int m = ((l+r)>>1);
//        cout << '*' << l << ' ' << r << ' ' << m << '\n';
        int mm = m, p = v;
//        cout << '=' << p << ' ';
        while(mm)
        {
            int z = __builtin_ctz(mm);
            mm -= LSO(mm);
            p = par[p][z];
//            cout <<  p << ' ';
        }
//        cout << '\n';
        if(tin[u] <= tin[p] && tout[p] <= tout[u])
            l = m+1;
        else
            r = m;
    }
    r = l-1;
    l = 0;
    ll d = M;
    while(l < r)
    {
        int m = ((l+r)>>1);
        int m1 = m, m2 = m+1, p1 = v, p2 = v;
        ll d1 = 0, d2 = 0;
        while(m1)
        {
            int z = __builtin_ctz(m1);
            m1 -= LSO(m1);
            d1 += sdp[p1][z];
            p1 = par[p1][z];
        }
        while(m2)
        {
            int z = __builtin_ctz(m2);
            m2 -= LSO(m2);
            d2 += sdp[p2][z];
            p2 = par[p2][z];
        }
        d1 += tcul[p1];
        d2 += tcul[p2];
        if(d1 < d2)
            r = m,
            d = d1;
        else
            l = m+1,
            d = d2;
    }
    return d;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    for(int i=0; i<N; i++) tcul[i] = M;
    memset(par, e, sizeof par);

    cin >> n >> s >> q >> e;
    for(int i=1; i<n; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        cel[i] = {u, v};
        graf[u].push_back({v, w});
        graf[v].push_back({u, w});
    }
    for(int i=0; i<s; i++)
    {
        int c; cin >> c;
        sh[c] = 1;
    }
    et(e, 0);
    dfsul(e, 0);
    dfs(e, e, 0);
//    for(int i=1; i<=n; i++)
//    {
//        cout << i << ": ";
//        for(int k=0; k<5; k++)
//            cout << sdp[i][k] << ' ';
//        cout << '\n';
//    }
    while(q--)
    {
        int r; cin >> bc >> r;
        int u = cel[bc].fi, v = cel[bc].se;
        if(tin[u] < tin[v] && tout[v] < tout[u])
        {
            if(tin[v] <= tin[r] && tout[r] <= tout[v])
            {
                ll aaa = bm(r, v);
                if(aaa == M) cout << "oo\n";
                else cout << aaa << '\n';
            }
            else cout << "escaped\n";
        }
        else
        {
            if(tin[u] <= tin[r] && tout[r] <= tout[u])
            {
                ll aaa = bm(r, u);
                if(aaa == M) cout << "oo\n";
                else cout << aaa << '\n';
            }
            else cout << "escaped\n";
        }
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...