제출 #1022067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022067		Almonther	Valley (BOI19_valley)	C++98	0 / 100	181 ms	173724 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
int n,s,q,e;
const int maxn=1e5+5,N=exp2(ceil(log2(maxn)));
vector<array<int,3>>v[maxn];
vector<int>shops;
int tre[N*4];
int num=1;
pair<int,int>node[maxn]={};
pair<int,int>par[maxn];
int depth[maxn];
vector<pair<int,int>>theroads;
pair<int,int>tab[maxn][20];
void dfs(int 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(int 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<int,int>lca(int a,int b){
    int diff=abs(depth[a]-depth[b]);
    int ans=0;
    if(diff){
        if(depth[a]<depth[b]){
            int 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]){
            int 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++){
        int 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++){
        int 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--){
        int del,idx;
        cin>>del>>idx;
        int copy=node[idx].first;
        int copy1=node[e].first;
        int 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{
            int dis=1e18;
            if(lca(a,copy).first==a){
                // auto it=lower_bound()
            }
            else{
                if(copy!=n){
                    if(lca(a,copy+1).first!=a){
                        dis=min(dis,lca(copy,copy+1).second);
                    }
                }
                if(copy!=1){
                    if(lca(a,copy-1).first!=a){
                        dis=min(dis,lca(copy,copy-1).second);
                    }
                }
            }
            co 0<<'\n';
        }
    }
}
int main()
{
    suiii
    int tt=1;
    // cin>>tt;
    while(tt--){
        solve();
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'void solve()':
valley.cpp:113:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
  113 |             int dis=1e18;
      |                     ^~~~

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