Submission #979817

#	Time	Username	Problem	Language	Result	Execution time	Memory
979817		Ludissey	Valley (BOI19_valley)	C++14	0 / 100	189 ms	49748 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;
int n,s,e,q;
vector<vector<pair<pair<int,int>,int>>> neigh;
vector<vector<int>> parent;
vector<int> depth;
vector<int> shop;
vector<int> dist;
vector<int> topdist;
vector<int> road;
vector<vector<pair<int,int>>> child;

const int LOG=31;

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

void make_tree(int x, int p){
    parent[x][0]=p;
    depth[x]=depth[p]+1;
    dist[x]+=dist[p];
    for (int j = 1; j < LOG; j++) parent[x][j]=parent[parent[x][j-1]][j-1];
    for (auto u : neigh[x])
    {
        if(u.first.first==p) continue;
        make_tree(u.first.first,x);
        child[x].push_back({u.first.first,u.first.second});
        road[u.second]=u.first.first;
        dist[u.first.first]=dist[x]+u.first.second;
    }
}

int nthparent(int a, int r){
    for (int j = LOG-1; j >= 0; j--) if(r&(1<<j)) a=parent[a][j];
    return a;    
}
int ddist(int a, int b){
    return abs(topdist[a]-topdist[b]);    
}

int dfs(int x,int d){
    topdist[x]=d;
    if(shop[x]) dist[x]=0;
    for (auto u : child[x])
    {
        dist[x]=min(dfs(u.first,d+u.second)+u.second,dist[x]);
    }
    return dist[x];
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin>>n>>s>>q>>e;
    e--;
    neigh.resize(n);
    depth.resize(n,0);
    child.resize(n);
    shop.resize(n,0);
    dist.resize(n,1e9);
    topdist.resize(n,0);
    road.resize(n-1,0);
    parent.resize(n, vector<int>(LOG));
    for (int i = 0; i < n-1; i++)
    {
        int a,b,w; cin >> a >> b >> w;
        a--; b--;
        neigh[a].push_back({{b,w},i});
        neigh[b].push_back({{a,w},i});
    }
    for (int i = 0; i < s; i++){
        int x; cin >> x;
        shop[x-1]=true;
    }
    make_tree(e, e);
    dfs(e,0);
    for (int i = 0; i < q; i++){
        int I,v; cin >> I >> v;
        v--;
        I--;
        int x=road[I];
        if(lca(x,v)==x){
            int mn=1e9;
            int l=0,r=depth[v]-depth[x];
            while(r-l>10){
                int midU=l+(l+r)/3;
                int midD=r-(l+r)/3;
                int npU=nthparent(x,midU);
                int npD=nthparent(x,midD);
                if(dist[npU]+ddist(v,npU)<dist[npD]+ddist(v,npD)){
                    r=midD;
                }else {
                    l=midU;
                }
            }
            for (int k = l; k <= r; k++) {
                mn=min(mn, dist[nthparent(v,k)]+ddist(v,nthparent(v,k)));
            }
            if(mn==1e9) cout << "oo\n";
            else cout << mn<<"\n";

        }else {
            cout << "escaped\n";
        }

    }
    return 0;
}

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