Submission #1022076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022076		Almonther	Valley (BOI19_valley)	C++98	0 / 100	166 ms	192704 KiB

valley

#include <bits/stdc++.h>

#define suiii ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define co cout<<
//#pragma GCC optimize("O3,Ofast,unroll-loops")
//#pragma GCC target("avx2,sse3,sse4,avx")
using namespace std;
//stuff
ll n,s,q,e;
const ll maxn=1e5+5,N=exp2(ceil(log2(maxn)));
vector<array<ll,3>>v[maxn];
vector<ll>shops;
ll tre[N*4];
ll num=1;
pair<ll,ll>node[maxn]={};
pair<ll,ll>par[maxn];
ll depth[maxn];
vector<pair<ll,ll>>theroads;
pair<ll,ll>tab[maxn][20];
void dfs(ll x){
    node[x]={num,0};
    depth[x]=depth[par[x].first]+1;
    num++;
    for(auto i:v[x]){
        if(i[1]==par[x].first) continue;
        par[i[1]]={node[x].first,i[2]};
        dfs(i[1]);
    }
    node[x]={node[x].first,num};
}
void maketable(ll x){
    if(x==0){
        for(int i=1;i<=n;i++){
            tab[i][x]=par[i];
        }
    }
    else{
        for(int i=1;i<=n;i++){
            tab[i][x].first=tab[tab[i][x-1].first][x-1].first;
            tab[i][x].second=tab[i][x-1].second+tab[tab[i][x-1].first][x-1].second;
        }
    }
}
pair<ll,ll>lca(ll a,ll b){
    ll diff=abs(depth[a]-depth[b]);
    ll ans=0;
    if(diff){
        if(depth[a]<depth[b]){
            ll curr=b;
            for(int i=19;i>=0;i--){
                if(((1<<i)&diff)>0){
                    ans+=tab[curr][i].second;
                    curr=tab[curr][i].first;
                }
            }
            b=curr;
        }
        else if(depth[a]>depth[b]){
            ll curr=a;
            for(int i=19;i>=0;i--){
                if(((1<<i)&diff)>0){
                    ans+=tab[curr][i].second;
                    curr=tab[curr][i].first;
                }
            }
            a=curr;
        }
    }
    if(a==b) return {a,ans};
    for(int i=19;i>=0;i--){
        if(tab[a][i].first!=tab[b][i].first&&tab[a][i].first!=0&&tab[b][i].first!=0){
            ans+=tab[a][i].second;
            a=tab[a][i].first;
            ans+=tab[b][i].second;
            b=tab[b][i].first;
        }
    }
    return {par[a].first,ans+par[a].second};
}
void solve(){
    cin>>n>>s>>q>>e;
    theroads.push_back({-1,-1});
    for(int i=1;i<n;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        v[a].push_back({c,b,i});
        v[b].push_back({c,a,i});
        theroads.push_back({a,b});
    }
    par[1]={0,0};
    dfs(1);
    for(int i=0;i<s;i++){
        ll a;
        cin>>a;
        shops.push_back(node[a].first);
    }
    sort(shops.begin(),shops.end());
    for(int i=0;i<=19;i++) maketable(i);
    while(q--){
        ll del,idx;
        cin>>del>>idx;
        ll copy=node[idx].first;
        ll copy1=node[e].first;
        ll a,b;
        a=node[theroads[del].first].first;
        b=node[theroads[del].second].first;
        if(depth[a]<depth[b]) swap(a,b);
        if((lca(a,copy).first==a&&lca(a,copy1).first==a)||(lca(a,copy).first!=a&&lca(a,copy1).first!=a)){
            co "escaped\n";
        }
        else{
            ll dis=1e18;
            if(lca(a,copy).first==a){
                auto it=lower_bound(shops.begin(),shops.end(),copy);
                auto it1=it--;
                if(it==shops.begin()){
                    if(lca(*it,a).first==a){
                        dis=min(dis,lca(*it,copy).second);
                    }
                }
                else if(it==shops.end()){
                    if(lca(*it1,a).first==a){
                        dis=min(dis,lca(*it1,copy).second);
                    }
                }
                else{
                    if(lca(*it,a).first==a){
                        dis=min(dis,lca(*it,copy).second);
                    }
                    if(lca(*it1,a).first==a){
                        dis=min(dis,lca(*it1,copy).second);
                    }
                }
            }
            else{
                auto it=lower_bound(shops.begin(),shops.end(),copy);
                auto it1=it--;
                if(it==shops.begin()){
                    if(lca(*it,a).first!=a){
                        dis=min(dis,lca(*it,copy).second);
                    }
                }
                else if(it==shops.end()){
                    if(lca(*it1,a).first!=a){
                        dis=min(dis,lca(*it1,copy).second);
                    }
                }
                else{
                    if(lca(*it,a).first!=a){
                        dis=min(dis,lca(*it,copy).second);
                    }
                    if(lca(*it1,a).first!=a){
                        dis=min(dis,lca(*it1,copy).second);
                    }
                }
            }
            if(dis!=1e18) co dis<<'\n';
            else co "oo"<<'\n';
        }
    }
}
int main()
{
    suiii
    int tt=1;
    // cin>>tt;
    while(tt--){
        solve();
    }
    return 0;
}

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