Submission #1105738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105738		koukirocks	Valley (BOI19_valley)	C++17	100 / 100	293 ms	62024 KiB

valley

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
template<typename T>
using vvector = vector<vector<T>>;

void dfs1(int v,int p,vvector<pll> &G,vector<ll> &h,vector<ll> &nsp,vvector<ll> &spt,vector<bool> &sp,vector<ll> &wh) {
    spt[v][0]=p;
    for (int k=1;k<20;k++) {
        spt[v][k]=spt[spt[v][k-1]][k-1];
    }
    h[v]=h[p]+1;
    nsp[v]=(sp[v]?0:oo);
    for (auto [i,w]:G[v]) {
        if (i==p) continue;
        wh[i]=wh[v]+w;
        dfs1(i,v,G,h,nsp,spt,sp,wh);
        nsp[v]=min(nsp[i]+w,nsp[v]);
    }
}

void dfs2(int v,int p,vvector<pll> &G,vvector<ll> &nspt,vvector<ll> &spt,vector<ll> &nsp,vector<ll> &h,vector<ll> &wh) {
    nspt[v][0]=nsp[v]-wh[v];
    for (int i=1;i<20;i++) nspt[v][i]=min(nspt[v][i-1],nspt[spt[v][i-1]][i-1]);
    for (auto [i,w]:G[v]) {
        if (i==p) continue;
        dfs2(i,v,G,nspt,spt,nsp,h,wh);
    }
}

int lca(int a,int b,vector<ll> &h,vvector<ll> &spt) {
    if (h[a]<h[b]) swap(a,b);
    int x=h[a]-h[b];
    for (int i=19;i>=0;i--) {
        if (x>=(1<<i)) {
            x-=(1<<i);
            a=spt[a][i];
        }
    }
    if (a==b) return a;
    for (int i=19;i>=0;i--) {
        if (spt[a][i]!=spt[b][i]) {
            a = spt[a][i];
            b = spt[b][i];
        }
    }
    return spt[a][0];
}

int main() {
    speed;
    int n,s,q,r;
    cin>>n>>s>>q>>r;
    vvector<pll> G(n+1);
    vector<bool> sp(n+1);
    vector<pii> e(n);
    for (int i=1;i<n;i++) {
        int a,b,w;
        cin>>a>>b>>w;
        e[i]={a,b};
        G[a].emplace_back(b,w);
        G[b].emplace_back(a,w);
    }
    for (int i=0;i<s;i++) {
        int x;
        cin>>x;
        sp[x]=true;
    }
    vector<ll> h(n+1),nsp(n+1),wh(n+1);
    vvector<ll> spt(n+1,vector<ll>(20));
    dfs1(r,0,G,h,nsp,spt,sp,wh);
    vvector<ll> nspt(n+1,vector<ll>(20));
    dfs2(r,0,G,nspt,spt,nsp,h,wh);
    while (q--) {
        int eid,x;
        cin>>eid>>x;
        if (h[e[eid].F]>h[e[eid].S]) swap(e[eid].F,e[eid].S);
        // cout<<x<<" "<<eid<<" "<<e[eid].F<<" "<<e[eid].S<<" x eid e\n";
        if (lca(x,e[eid].S,h,spt)!=e[eid].S) cout<<"escaped\n";
        else {
            ll ans=nsp[x]-wh[x];
            ll d = h[x]-h[e[eid].S]+1;
            int tx=x;
            for (int i=19;i>=0;i--) {
                if (d>=(1<<i)) {
                    ans=min(ans,nspt[x][i]);
                    x = spt[x][i];
                    d-=(1<<i);
                }
            }
            ans += wh[tx];
            if (ans>=oo) cout<<"oo\n";
            else cout<<ans<<"\n";
        }
    }
    return 0;
}

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