Submission #424437

#	Time	Username	Problem	Language	Result	Execution time	Memory
424437		Odavey	Valley (BOI19_valley)	C++17	100 / 100	654 ms	96600 KiB

valley

//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            200005
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

int _in[MX_N], _out[MX_N];
int glit = 0;

ll mass[MX_N];
vector<pair<int, int> > adj[MX_N];
int p[MX_N];
int c[MX_N];

ll depth[MX_N];
ll minn[MX_N];//The cost of choosing this node as the "LCA". ie the second part of dist[u] + dist[v] - 2*dist[w]
int jump[MX_N][48];
ll minn_jump[MX_N][48];//The minimum cost value in the step above at
bool shoppe[MX_N];

void DFS(int at){
    _in[at] = glit++;
    minn[at] = INF;
    for(auto& [to, id] : adj[at]){
        if(p[at] == to){
            continue;
        }
        c[id] = to;
        p[to] = at;
        depth[to] = mass[id] + depth[at];
        DFS(to);
        minn[at] = min(minn[at], minn[to]);
    }
    if(shoppe[at]){
        minn[at] = depth[at];
    }
    _out[at] = glit++;
    return;
}

bool desc(int a, int b){
    return(_in[a] >= _in[b] && _out[a] <= _out[b]);
}

int main(){
    memset(shoppe, 0, sizeof(shoppe));
    memset(jump, -1, sizeof(jump));
    int n, s, Q, E;
    cin >> n >> s >> Q >> E;
    --E;
    p[E] = -1;
    depth[E] = 0ll;
    for(int i=0;i<n-1;++i){
        int A, B;
        cin >> A >> B >> mass[i];
        --A, --B;
        adj[A].pb({B, i});
        adj[B].pb({A, i});
    }
    for(int i=0;i<s;++i){
        int at;
        cin >> at;
        --at;
        shoppe[at] = true;
    }
    DFS(E);

    for(int at=0;at<n;++at){
        if(minn[at] != INF){
            minn[at] -= 2ll*depth[at];
        }
        jump[at][0] = p[at];
        minn_jump[at][0] = minn[at];
    }
    for(int k=1;k<48;++k){
        for(int at=0;at<n;++at){
            if(jump[at][k-1] == -1){
                jump[at][k] = -1;
                minn_jump[at][k] = INF;
            }else{
                jump[at][k] = jump[jump[at][k-1]][k-1];
                minn_jump[at][k] = min(minn_jump[at][k-1], minn_jump[jump[at][k-1]][k-1]);
            }
        }
    }
//    cout << "minn:\n";
//    for(int i=0;i<n;++i){
//        cout << minn[i] << endl;
//    }
//    cout << "jump:\n";
//    for(int i=0;i<n;++i){
//        for(int k=0;k<4;++k){
//            cout << jump[i][k] << ' ';
//        }
//        cout << endl;
//    }
//    cout << "minn_jump\n";
//    for(int i=0;i<n;++i){
//        for(int k=0;k<4;++k){
//            cout << minn_jump[i][k] << ' ';
//        }
//        cout << endl;
//    }

    for(int q=0;q<Q;++q){
        int r, v;
        cin >> r >> v;
        --r, --v;
        if(!desc(v, c[r])){
            cout << "escaped\n";
            continue;
        }
        int at = v;
        ll ans = min(minn[v], minn[c[r]]);
        for(int k=47;~k;--k){
            if(jump[at][k] == -1){
                continue;
            }
            if(!desc(jump[at][k], c[r])){
                continue;
            }
            ans = min(ans, minn_jump[at][k]);
            at = jump[at][k];
        }
        if(ans == INF){
            cout << "oo\n";
        }else{
            cout << depth[v] + ans << endl;
        }
    }
}

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