Submission #1100522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100522		tinnhiemnn	Valley (BOI19_valley)	C++17	100 / 100	151 ms	43760 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define file "file"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
const int N=1e5+5;
const long long INF=1e18;
int n,s,q,H,up[N][22],d[N];
long long h[N],lift[N][22],ss[N];
vector<pii> E[N], edge;
bool a[N];

void dfs(int u)
{
    if (a[u]) ss[u]=h[u]; else ss[u]=INF;
    for (pii p : E[u])
    {
        int v=p.first; if (v==up[u][0]) continue;
        up[v][0]=u; d[v]=d[u]+1; h[v]=h[u] + p.second;

        for (int j=1;j<=20;j++) up[v][j]=up[up[v][j-1]][j-1];
        dfs(v);
        ss[u]=min(ss[u], ss[v]);
    }
}
int lca(int u, int v)
{
    if (d[u]!=d[v])
    {
        if (d[u] < d[v]) swap(u, v);
        int k=d[u]-d[v];
        for (int j=0;(1<<j) <= k;j++)
            if ((k>>j) & 1) u=up[u][j];
    }
    if (u==v) return u;
    int k=__lg(d[u]);
    for (int j=k;j>=0;j--)
        if (up[u][j]!=up[v][j]) u=up[u][j], v=up[v][j];
    return up[u][0];
}
long long get(int u, int v)
{
    long long res=INF;
    for (int j=20;j>=0;j--)
        if (up[u][j]>0 && lca(up[u][j], v) == v)
    {
        res=min(res, lift[u][j]); u=up[u][j];
    }
    return min(res, ss[v]);
}
int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n>>s>>q>>H;
    for (int i=1;i<n;i++)
    {
        int u,v,w; cin>>u>>v>>w; E[u].pb({v, w}); E[v].pb({u, w}); edge.pb({u, v});
    }
    for (int i=1;i<=s;i++) {int x; cin>>x; a[x]=1;}

    dfs(H);
    //for (int i=1;i<=n;i++) cout<<ss[i]<<' '; cout<<endl;
    for (int i=1;i<=n;i++)
    {
        if (ss[i]<INF) ss[i]-=2*h[i];
        lift[i][0]=ss[i];
    }

    for (int j=1;j<=20;j++)
        for (int i=1;i<=n;i++) lift[i][j]=min(lift[i][j-1], lift[up[i][j-1]][j-1]);

    for (int i=0;i<edge.size();i++)
        if (d[edge[i].first] > d[edge[i].second]) swap(edge[i].first, edge[i].second);

    while (q--)
    {
        int x,u; cin>>x>>u; x--;
        if (lca(u, edge[x].second) != edge[x].second) {cout<<"escaped\n"; continue;}

        long long res=get(u, edge[x].second) + h[u];
        if (res<INF) cout<<res<<'\n'; else cout<<"oo\n";
    }


}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i=0;i<edge.size();i++)
      |                  ~^~~~~~~~~~~~

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