oj.uz

Submission #1100520

# Submission time Handle Problem Language Result Execution time Memory
1100520 2024-10-14T07:35:20 Z tinnhiemnn Valley (BOI19_valley) C++17
0 / 100
 82 ms 52632 KB 
#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;
int n,s,q,H,up[N][22],d[N],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]=INT_MAX;
    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];
}
int get(int u, int v)
{
    int res=INT_MAX;
    for (int j=20;j>=0;j--)
        if (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]<INT_MAX) 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;}

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


}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:75: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]
   75 |     for (int i=0;i<edge.size();i++)
      |                  ~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4688 KB Output is correct
2 Runtime error 7 ms 8976 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4688 KB Output is correct
2 Runtime error 7 ms 8976 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 52632 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4688 KB Output is correct
2 Runtime error 7 ms 8976 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -