제출 #1192710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192710		Newtonabc	Valley (BOI19_valley)	C++20	100 / 100	103 ms	22088 KiB

valley

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=1<<18;
vector<pair<int,long long>> adj[N];
int ti,in[N],out[N],pa[N],dep[N],top[N],sz[N];
bool sh[N];
//distance from root, constant c[x]=min(d[shop])-2*d[x], dp[i]=minimum distance from root to shop in subtree of node i
long long d[N],c[N],dp[N],s[M];
pair<int,int> edge[N];
void build(int l,int r,int idx){
    s[idx]=LLONG_MAX;
    if(l==r) return;
    int m=(l+r)/2;
    build(l,m,idx*2);
    build(m+1,r,idx*2+1);
}
void update(int l,int r,int idx,int a,long long b){
    if(a<l || a>r) return;
    if(l==r){
        s[idx]=b;
        return;
    }
    int m=(l+r)/2;
    update(l,m,idx*2,a,b);
    update(m+1,r,idx*2+1,a,b);
    s[idx]=min(s[idx*2],s[idx*2+1]);
}
long long query(int l,int r,int idx,int a,int b){
    if(b<l || a>r) return LLONG_MAX;
    if(a<=l && b>=r) return s[idx];
    int m=(l+r)/2;
    return min(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
}
void findsz(int u,int p=0){
    sz[u]=1;
    int tmp=sz[p];
    sz[p]=0;
    for(int i=0;i<adj[u].size();i++){
        auto [v,w]=adj[u][i];
        if(v==p) continue;
        dep[v]=dep[u]+1;
        findsz(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[adj[u][0].first]) swap(adj[u][i],adj[u][0]);
    }
    sz[p]=tmp;
}
void dfs(int u,int p=-1){
    in[u]=++ti;
    for(auto [v,w]:adj[u]){
        if(v==p) continue;
        pa[v]=u;
        d[v]=d[u]+w;
        if(v==adj[u][0].first) top[v]=top[u];
        else top[v]=v;
        dfs(v,u);
    }
    out[u]=ti;
}
void efs(int u,int p=-1){
    if(sh[u]) dp[u]=d[u];
    else dp[u]=LLONG_MAX;
    for(auto [v,w]:adj[u]){
        if(v==p) continue;
        efs(v,u);
        dp[u]=min(dp[u],dp[v]);
    }
}
long long path(int u,int v){
    long long ans=LLONG_MAX;
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]) swap(u,v);
        ans=min(ans,query(1,ti,1,in[top[v]],in[v]));
        v=pa[top[v]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    ans=min(ans,query(1,ti,1,in[u],in[v]));
    return ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,ss,q,e;
    cin>>n >>ss >>q >>e;
    for(int i=0;i<n-1;i++){
        int a,b;
        long long c;
        cin>>a >>b >>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
        edge[i+1]={a,b};
    }
    for(int i=0;i<ss;i++){
        int inp;
        cin>>inp;
        sh[inp]=true;
    }
    top[e]=e;
    findsz(e);
    dfs(e);
    efs(e);
    // for(int i=1;i<=n;i++) cout<<sh[i] <<" ";
    // cout<<"\n";
    // for(int i=1;i<=n;i++) cout<<dp[i] <<" ";
    // cout<<"\n";
    build(1,ti,1);
    for(int i=1;i<=n;i++){
        if(dp[i]!=LLONG_MAX) c[i]=dp[i]-2LL*d[i];
        else c[i]=LLONG_MAX;
        update(1,ti,1,in[i],c[i]);
    }
    // for(int i=1;i<=n;i++) cout<<c[i] <<" ";
    // cout<<"\n";
    while(q--){
        int clo,f;
        cin>>clo >>f;
        auto [hi,lo]=edge[clo];
        if(pa[lo]!=hi) swap(lo,hi);
        if(!(in[f]>=in[lo] && out[f]<=out[lo])){
            cout<<"escaped\n";
            continue;
        }
        if(dp[lo]==LLONG_MAX){
            cout<<"oo\n";
            continue;
        }
        long long ans=d[f]+path(lo,f);
        cout<<ans <<"\n";
    }
}

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