Submission #979898

#	Time	Username	Problem	Language	Result	Execution time	Memory
979898		Ludissey	Valley (BOI19_valley)	C++14	23 / 100	328 ms	55824 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<bool> 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(d&(1<<i)) 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){
    for (auto u : neigh[x])
    {
        if(u.first.first==p) continue;
        parent[u.first.first][0]=x;
        depth[u.first.first]=depth[x]+1;
        for (int j = 1; j < LOG; j++) parent[u.first.first][j]=parent[parent[u.first.first][j-1]][j-1];
        child[x].push_back({u.first.first,u.first.second});
        road[u.second]=u.first.first;
        make_tree(u.first.first,x);
    }
}
 
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];
}

int full_dist(int a, int b){
    return dist[b]+ddist(a,b);
}
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,false);
    dist.resize(n,1e9);
    topdist.resize(n,0);
    road.resize(n-1,0);
    parent.resize(n, vector<int>(LOG,e));
    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);
    topdist[e]=0;
    for (int i = 0; i < q; i++){
        int _I,v; cin >> _I >> v;
        v--;
        _I--;
        int _v=v;
        int x=road[_I];
        if(lca(x,v)==x){
            int mn=1e9;
            int r=depth[v]-depth[x];
            int c=0;
            for (int j = LOG-1; j >= 0; j--) {
                if(full_dist(v,parent[_v][j])<full_dist(v,_v)&&c+(1<<j)<=r) {
                    _v=parent[_v][j];
                    c+=(1<<j);
                }
            }
            mn=full_dist(v,_v);
            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: 23 / 23
• Subtask 4: 0 / 41