Submission #1310145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310145		Ludissey	Valley (BOI19_valley)	C++17	100 / 100	217 ms	80308 KiB

valley

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;

const int LOG=24;

int n,s,e,q;
vector<vector<pair<int,int>>> neigh;
vector<bool> sp;
vector<int> depth;
vector<vector<int>> up;
vector<vector<int>> down;
vector<vector<pair<int,int>>> parent;

void dfs(int x, int p){
    if(sp[x]) down[x][0]=0;
    for (auto u : neigh[x])
    {
        if(u.first==p) continue;
        parent[u.first][0]={x,u.second};
        depth[u.first]=depth[x]+1;
        dfs(u.first, x);
        down[x][0]=min(down[x][0],down[u.first][0]+u.second);
    }
}


int lca(int a, int b){
    if(depth[a]>depth[b]) swap(a,b);
    int d=depth[b]-depth[a];
    for (int j = LOG-1; j >= 0; j--)
    {
        if(d&(1<<j)) b=parent[b][j].first;
    }
    if(a==b) return a;
    for (int j = LOG-1; j >= 0; j--)
    {
        if(parent[a][j].first!=parent[b][j].first) a=parent[a][j].first,b=parent[b][j].first;
    }
    return parent[a][0].first;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin>>n>>s>>q>>e;
    neigh.resize(n);
    depth.resize(n,0);
    sp.resize(n,false);
    down.resize(n,vector<int>(LOG,1e15));
    parent.resize(n,vector<pair<int,int>>(LOG));
    vector<pair<int,int>> edge(n-1);
    
    e--;
    for (int i = 0; i < n-1; i++)
    {
        int a,b,w; cin >> a >> b >> w;
        a--; b--;
        edge[i]={a,b};
        neigh[a].push_back({b,w});
        neigh[b].push_back({a,w});
    }
    for (int i = 0; i < s; i++){
        int x; cin >> x;
        sp[x-1]=true;
    }

    parent[e][0]={e,0};
    depth[e]=0;
    dfs(e,-1);
    for (int j = 1; j < LOG; j++)
    {
        for (int i = 0; i < n; i++)
        {
            parent[i][j]={parent[parent[i][j-1].first][j-1].first,parent[parent[i][j-1].first][j-1].second+parent[i][j-1].second};

            down[i][j]=min(down[i][j-1],down[parent[i][j-1].first][j-1]+parent[i][j-1].second);
        }
    }
    for (int i = 0; i < q; i++)
    {
        int I; cin >> I; I--;
        int r; cin >> r; r--;
        int a=edge[I].first; int b=edge[I].second;
        if(depth[b]<depth[a]) swap(a,b);
        
        if(lca(b,r)!=b){
            cout << "escaped\n";
            continue;
        } 
        int d=depth[r]-depth[b];
        int dst=0;
        int x=r;
        int mn=1e15;
        for (int j = LOG-1; j >= 0; j--)
        {
            if(d&(1<<j)){
                mn=min(down[x][j]+dst,mn);
                dst+=parent[x][j].second;
                x=parent[x][j].first;
            }
        }
        mn=min(down[x][0]+dst,mn);
        if(mn==1e15) cout << "oo\n";
        else cout << mn << "\n";
    }
        
    
    return 0;
}

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