Submission #633172

#	Time	Username	Problem	Language	Result	Execution time	Memory
633172		Iwanttobreakfree	Valley (BOI19_valley)	C++17	59 / 100	557 ms	39496 KiB

valley

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define int long long
#define pii pair<int,int>
int logn=18;
struct CELL{
    int node,w,id;
};
int t=0;
bool is_ancestor(int a,int b,vector<pii>& time){
    if(time[a].first<time[b].first&&time[a].second>time[b].second)return true;
    return false;
}
int get_par(int a,int x,vector<vector<int>>& par){
    for(int i=logn-1;i>=0;i--){
        if(x&(1<<i))a=par[a][i];
    }
    return a;
}
bool escape(int anc,int x,vector<vector<int>>& p,vector<int>& depth,vector<pii>& time){
    int dif=depth[x]-depth[anc];
    if(get_par(x,dif,p)==anc)return false;
    return true;
}
void dfs(int a,int par,vector<vector<CELL>>& g,vector<pii>& time,vector<vector<int>>& p,vector<int>& depth){
    time[a].first=t;
    t++;
    p[a][0]=par;
    depth[a]=depth[par]+1;
    for(int j=1;j<logn;j++){
        p[a][j]=p[p[a][j-1]][j-1];
    }
    for(auto v:g[a]){
        if(par==v.node)continue;
        dfs(v.node,a,g,time,p,depth);
    }
    time[a].second=t;
    t++;
}
int dijkstra(int a,int i,vector<vector<CELL>>& g,vector<int>& shop){
    priority_queue<pii> pq;
    pq.push({0,a});
    int n=g.size();
    vector<int> dist(n,1e18);
    dist[a]=0;
    while(!pq.empty()){
        int u=pq.top().second,d=-pq.top().first;
        pq.pop();
        if(dist[u]<d)continue;
        for(auto v:g[u]){
            if(v.id==i)continue;
            if(dist[v.node]>dist[u]+v.w){
                dist[v.node]=dist[u]+v.w;
                pq.push({-dist[v.node],v.node});
            }
        }
    }
    int ans=1e18;
    for(int s:shop){
        ans=min(ans,dist[s]);
    }
    return ans;
}
signed main(){
    int n,s,q,e,x,y,w;
    cin>>n>>s>>q>>e;
    e--;
    vector<pii> edges(n-1),time(n);
    vector<vector<CELL>> g(n,vector<CELL>());
    vector<vector<int>> p(n,vector<int>(logn));
    vector<int> shop(s),depth(n);
    for(int i=0;i<n-1;i++){
        cin>>x>>y>>w;
        x--;y--;
        g[x].push_back({y,w,i});
        g[y].push_back({x,w,i});
        edges[i]={x,y};
    }
    for(int i=0;i<s;i++){
        cin>>shop[i];
        shop[i]--;
    }
    dfs(e,e,g,time,p,depth);
    //for(int i=0;i<n;i++)cout<<depth[i]<<' ';
    while(q--){
        cin>>x>>y;
        x--;y--;
        int anc=edges[x].first;
        if(time[edges[x].second]>time[anc])anc=edges[x].second;
        //cout<<anc<<'\n';
        if(escape(anc,y,p,depth,time))cout<<"escaped\n";
        else{
            if(n*q>1e6){
                cout<<"0\n";
            }else{
                int ans=dijkstra(y,x,g,shop);
                if(ans==1e18)cout<<"oo\n";
                else cout<<ans<<'\n';
            }
        }
    }
}

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