Submission #1213272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213272		minhpk	Valley (BOI19_valley)	C++20	100 / 100	277 ms	104596 KiB

valley

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

const int MAXN = 100005;
const int INF = 1e17;


vector<pair<int,int>> z[MAXN];
pair<int,int> canh[MAXN];
int high[MAXN];
int low[MAXN];
int check[MAXN];
int up[MAXN][25];
int g[MAXN][25];
int val[MAXN][25];
int sta[MAXN];
int fin[MAXN];
int rev[MAXN];
int tour;
int a, s, q, e;
int down[MAXN][25];
int dis[MAXN];
int fwd[25];

struct node{
    pair<int,int> st,nd,rd;
};
node low1[1000000];


void update(int i,int val,int p){
    if (val<=low1[i].st.first){
        low1[i].rd=low1[i].nd;
        low1[i].nd=low1[i].st;
        low1[i].st={val,p};
    }else if (val<=low1[i].nd.first){
        low1[i].rd=low1[i].nd;
        low1[i].nd={val,p};
    }else if (val<=low1[i].rd.first){
        low1[i].rd={val,p};
    }
}



void dfs(int i, int par) {
    tour++;
    sta[i] = tour;
    rev[tour] = i;
    low[i] = INF;
    if (check[i]) {
        low[i] = 0;
        update(i,0,i);
    }
    for (auto p : z[i]) {
        if (p.first == par) continue;
        high[p.first] = high[i] + 1;
        dis[p.first] = dis[i] + p.second;
        dfs(p.first, i);
        update(i,low[p.first]+p.second,p.first);
        low[i] = min(low[i], low[p.first] + p.second);
    }
    fin[i] = tour;
}

void dfs1(int i, int par) {
    up[i][0] = par;
    for (int j = 1; j <= 20; j++) {
        up[i][j] = up[up[i][j - 1]][j - 1];
        g[i][j] = g[up[i][j - 1]][j - 1] + g[i][j - 1];
        val[i][j] = min(val[i][j - 1], val[up[i][j - 1]][j - 1] + g[i][j - 1]);
        down[i][j] = min(down[i][j - 1], down[up[i][j - 1]][j - 1]);
    }
    int max1 = INF, max2 = INF;
    int trace = 0, id = 0;
    if (check[i]) {
        max1 = 0;
        trace = 0;
        id = 0;
    }
    for (auto p : z[i]) {
        if (p.first == par) continue;
        if (max1 > low[p.first] + p.second) {
            max1 = low[p.first] + p.second;
            trace = p.first;
            id = p.second;
        }
    }
    for (auto p : z[i]) {
        if (p.first == par) continue;
        if (p.first == trace) continue;
        if (max2 > low[p.first] + p.second) {
            max2 = low[p.first] + p.second;
        }
        g[p.first][0] = p.second;
        val[p.first][0] = p.second + max1;
        down[p.first][0] = max1 + dis[i];
        dfs1(p.first, i);
    }
    if (trace) {
        g[trace][0] = id;
        val[trace][0] = id + max2;
        down[trace][0] = max2 + dis[i];
        dfs1(trace, i);
    }
}
int lca(int x,int y){
   if (high[x]<high[y]){
       swap(x,y);
   }

   for (int i=20;i>=0;i--){
       if (high[up[x][i]]>=high[y]){
           x=up[x][i];
       }
   }
 //  cout << x << " " << y << '\n';
   if (x==y){
       return x;
   }

   for (int i=20;i>=0;i--){
       if (up[x][i]!=up[y][i] && up[x][i]!=0){
           x=up[x][i];
           y=up[y][i];
       }
   }
   return up[x][0];
}

int caldis(int x,int y){
    if (high[x]<high[y]){
        swap(x,y);
    }
    int cnt=0;
    for (int i=20;i>=0;i--){
         if (high[up[x][i]]>=high[y]){
             cnt+=g[x][i];
             x=up[x][i];
         }
    }
    if (x==y){
        return cnt;
    }
    for (int i=20;i>=0;i--){
       if (up[x][i]!=up[y][i] && up[x][i]!=0){
           cnt+=g[x][i];
           cnt+=g[y][i];

           x=up[x][i];
           y=up[y][i];
       }
   }

   return cnt+g[x][0]+g[y][0];
}

bool check1(int p,int x){
   // cout << sta[x] << " " << fin[x] << "\n";
    bool req1 = (sta[p] >= sta[x] && sta[p] <= fin[x] && sta[e] >= sta[x] && sta[e] <= fin[x]);
    bool req2 = ((sta[p] < sta[x] || sta[p] > fin[x]) && (sta[e] < sta[x] || sta[e] > fin[x]));
    return (req1 || req2);
}


signed main() {
   // freopen("test.txt", "r", stdin);
   // freopen("o2.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> s >> q >> e;
    fwd[0] = 1;
    for (int i = 1; i <= 20; i++) {
        fwd[i] = fwd[i - 1] * 2;
    }
    for (int i = 1; i < a; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        canh[i] = {x, y};
        z[x].push_back({y, t});
        z[y].push_back({x, t});
    }
    for (int i = 1; i <= s; i++) {
        int x;
        cin >> x;
        check[x] = 1;
    }

    for (int i=1;i<=a;i++){
        low1[i].st={1e17,1};
        low1[i].nd={1e17,1};
        low1[i].rd={1e17,1};
    }
    high[0]=-1;
    dfs(e, 0);
    dfs1(e, 0);



   // for (int i=1;i<=a;i++){
   //     cout << low[i] << "\n";
  //  }
    while (q--) {
        int road, p;
        cin >> road >> p;
        int x = canh[road].first;
        int y = canh[road].second;

        int dis1=caldis(x,p);
        int dis2=caldis(y,p);
        if (dis1>dis2){
            swap(x,y);
        }


       int l=lca(p,x);
       int l1=lca(p,y);

       // cout << x <<  " " << p << "\n";
      //  cout << l << " " << l1 << "\n";
        if (l!=x || l1!=y) {
            cout << "escaped" << "\n";
            continue;
        }

        int ans=INF;
        //cout << sta[x] << " " << sta[p] << "\n";
        if (sta[x]<sta[p] || sta[x]>fin[p]){

            ans=min(ans,low[p]);
            //cout << "ok" << "\n";
        }
       // cout << ans << "\n";
        if (check[p]){
            ans=0;
        }
        int pos1,pos2;

        int distance = high[p] - high[l]-1;
        int t_node = p;
        int cur = 0;
        int step = 0;
        for (int i = 20; i >= 0; i--) {
            if (step + fwd[i] <= distance) {
                    ans = min(ans, val[t_node][i] + cur);
                    cur += g[t_node][i];
                    t_node = up[t_node][i];
                    step += fwd[i];
            }
        }
        pos1=t_node;
        if (pos1==l){
            pos1=-1;
        }
         distance = high[x] - high[l]-1;
         t_node = x;
         cur = 0;
         step = 0;
        for (int i = 20; i >= 0; i--) {
            if (step + fwd[i] <= distance) {
                    ans = min(ans, down[t_node][i] -dis[l] + (dis[p]-dis[l]));

                    t_node = up[t_node][i];
                    step += fwd[i];
            }
        }
        pos2=t_node;
        if (x==l){
            pos2=-1;
        }
       // cout << pos1 << " " << pos2 << "\n";
        int preans;
        if (low1[l].st.second==pos1 ||low1[l].st.second==pos2 ){
            if (low1[l].nd.second==pos1 || low1[l].nd.second==pos2){
               // cout << "ok" << "\n";
                preans=low1[l].rd.first+dis[p]-dis[l];
            }else{
                //cout << "ok" << "\n";
                preans=low1[l].nd.first+dis[p]-dis[l];
            }
        }else{
               // cout << "ok" << " ";
              //  cout << low1[l].st.first << "\n";
              //  cout << "ok" << "\n";
                preans=low1[l].st.first+dis[p]-dis[l];
        }

        // cout << preans << "\n";
        ans=min(ans,preans);
        if (sta[p]<sta[x] || sta[p]>fin[x]){
            int distance = high[1] - high[l];
            int t_node = l;
            int cur = 0;
            int step = 0;
            for (int i = 20; i >= 0; i--) {
               if (step + fwd[i] <= distance) {
                    ans = min(ans, val[t_node][i] + cur);
                    cur += g[t_node][i];
                    t_node = up[t_node][i];
                    step += fwd[i];
               }
            }
        }


        if (ans>=INF){
            cout << "oo" << "\n";
        }else{
            cout << ans << "\n";
        }


    }
    return 0;
}


/*
freopen("test.txt", "r", stdin);
    freopen("o2.out", "w", stdout);
*/

/*
10 3 2 2
1 1 0
1 1 0
0 1 1
1 0 0
1 1 0
1 0 1
1 0 1
1 1 0
0 0 1
0 1 1
0
0
*/

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