Submission #1305384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305384		veham	Valley (BOI19_valley)	C++20	0 / 100	316 ms	77504 KiB

valley

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
struct edge{
    ll v;
    ll w;
};
bool operator<(edge a, edge b){return a.w > b.w;}
bool operator==(edge a, edge b){return make_pair(a.v,a.w) == make_pair(b.v,b.w);};
typedef vector<edge> ve;
typedef vector<ve> vve;
#define MAX 1e17

struct Node{
    ll l,r;
    ll v = MAX;
    Node *LC = nullptr, *RC = nullptr;
    Node(ll l, ll r) : l(l), r(r) {
        if(l != r){
            LC = new Node(l,(l+r)/2);
            RC = new Node((l+r)/2+1,r);
        }
    }
    Node(){}

    ll query(ll i, ll j){
        if(i > r || j < l) return MAX;
        if(i <= l && j >= r) return v;
        return min(LC->query(i,j),RC->query(i,j));
    }

    void update(ll i, ll x){
        if(i > r || i < l) return;
        if(l == r){
            v = min(x,v);
            return;
        }
        LC->update(i,x);
        RC->update(i,x);
        v = min(LC->v,RC->v);
    }
};

struct Solve{
    ll N,Q,E;
    vi A,B,S,I,R,D,Pre,Inv,Sz,HC,HR;
    ve F;
    vl W,DS,Ans,H;
    vve G,C;
    vvi BL,VQ;
    vvl DBL;
    Node Seg;

    void DFS(ll v, edge prev){
        F[v] = prev;
        D[v] = D[prev.v] + 1;
        H[v] = H[prev.v] + prev.w;
        Pre.push_back(v);
        for(edge e : G[v]){
            if(e == prev) continue;
            C[v].push_back(e);
            DFS(e.v,{v,e.w});
            Sz[v] += Sz[e.v];
        }
    }

    void DFS15(ll v, bool ish = 0){
        if(ish) HR[v] = HR[F[v].v];
        else HR[v] = v;
        Pre.push_back(v);
        if(C[v].empty()) return;
        HC[v] = max_element(C[v].begin(),C[v].end(),[&](edge a, edge b){return Sz[a.v] < Sz[b.v];})->v;
        DFS15(HC[v],1);
        for(edge e : C[v]){
            if(e.v == HC[v]) continue;
            DFS15(e.v);
        }
    }

    ll LCA(ll v, ll u){
        if(D[u] > D[v]) swap(u,v);
        if(D[u] < D[v]){
            for(ll d = D[v] - D[u],b = 0;b < BL.size();b++){
                if(d & (1<<b)) v = BL[b][v];
            }
        }
        if(u == v) return u;
        for(ll b = BL.size()-1;b >= 0;b--) if(BL[b][v] != BL[b][u]) v = BL[b][v],u = BL[b][u];
        return BL[0][u];
    }

    // ll distu(ll u, ll n){
    //     ll ans = 0;
    //     for(ll b = 0;b < BL.size();b++){
    //         if(n & (1<<b)) ans += DBL[b][u], u = BL[b][u];
    //     }
    // }

    ll query(ll v, ll r){
        ll ans = MAX;
        ll c = r;
        for(;D[HR[c]] > D[v];c = F[HR[c]].v) ans = min(ans,Seg.query(Inv[HR[c]],Inv[c]));
        ans = min(ans,Seg.query(Inv[v],Inv[c]));
        return ans;
    }

    void DFS2(ll v){
        for(edge e : C[v]){
            DFS2(e.v);
            DS[v] = min(DS[v],DS[e.v] + 2*e.w);
        }
        if(S[v]) DS[v] = -H[v];
        Seg.update(Inv[v],DS[v]);
        for(ll q : VQ[v]){
            if(LCA(v,R[q]) != v) Ans[q] = -1;
            else Ans[q] = query(v,R[q]) + H[R[q]];
        }
    }

    Solve(ll N, ll Q, ll E, vi A, vi B, vi S, vi I, vi R, vl W) : N(N), Q(Q), E(E), A(A), B(B), S(S), I(I), R(R), W(W) {
        BL.assign(ll(log2(N)+1),vi(N));
        DBL.assign(ll(log2(N)+1),vl(N));
        D.assign(N,-1);
        H.assign(N,0);
        Sz.assign(N,1);
        G.assign(N,{});
        F.assign(N,{0,0});
        C.assign(N,{});
        HR.assign(N,0);
        HC.assign(N,0);
        for(ll i = 0;i < N-1;i++){
            G[A[i]].push_back({B[i],W[i]});
            G[B[i]].push_back({A[i],W[i]});
        }
        DFS(E,{E,0});
        Inv.assign(N,0);
        for(ll i = 0;i < N;i++) Inv[Pre[i]] = i;
        DFS15(E);
        for(ll i = 0;i < N;i++) BL[0][i] = F[i].v, DBL[0][i] = F[i].w;
        for(ll p = 1;p < BL.size();p++){
            for(ll i = 0;i < N;i++){
                BL[p][i] = BL[p-1][BL[p-1][i]];
                DBL[p][i] = DBL[p-1][i] + DBL[p-1][BL[p-1][i]];
            }
        }
        for(ll i = 0;i < N-1;i++) if(D[A[i]] < D[B[i]]) swap(A[i],B[i]);
        VQ.assign(N,{});
        for(ll i = 0;i < Q;i++) VQ[A[I[i]]].push_back(i);
        Ans.assign(Q,0);
        DS.assign(N,MAX);
        Seg = Node(0,N-1);
        DFS2(E);
    }
};

int main(){
    ll N,S,Q,E;
    cin >> N >> S >> Q >> E;
    E--;
    vi A(N-1),B=A,Sh(S),IS(N,0),I(Q),R(Q);
    vl W(N-1);
    for(ll i = 0;i < N-1;i++){
        cin >> A[i] >> B[i] >> W[i];
        A[i]--,B[i]--;
    }
    for(ll i = 0;i < S;i++){
        cin >> Sh[i];
        IS[--Sh[i]] = 1;
    }
    for(ll i = 0;i < Q;i++){
        cin >> I[i] >> R[i];
        I[i]--,R[i]--;
    }

    Solve sol(N,Q,E,A,B,IS,I,R,W);
    for(ll a : sol.Ans){
        if(a == -1) cout << "escaped\n";
        else if(a == MAX) cout << "oo\n";
        else cout << a << '\n';
    }
    return 0;
}

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