oj.uz

Submission #867615

# Submission time Handle Problem Language Result Execution time Memory
867615 2023-10-29T01:29:45 Z 12345678 Valley (BOI19_valley) C++17
100 / 100
 160 ms 55892 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5, kx=17;
ll n, s, q, e, u, v, w, mnd[nx], mn[nx][kx], pa[nx][kx], ans[nx], lvl[nx], dp[nx], qs[nx], x, y, cnt;
vector<tuple<ll, ll, ll>> d[nx];
vector<pair<ll, ll>> t[nx];
bool pw[nx];

void dfs(int u, int p)
{
    //cout<<"here"<<' '<<u<<' '<<mnd[u]<<'\n';
    pa[u][0]=p;
    lvl[u]=lvl[p]+1;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, w, i]:d[u])
    {
        if (v==p) continue;
        qs[v]=qs[u]+w;
        dfs(v, u);
        mnd[u]=min(mnd[u], mnd[v]+w);
    }
    if (pw[u]) mnd[u]=0;
}

void dfs2(int u, int p)
{
    for (int i=1; i<kx; i++) mn[u][i]=min(mn[u][i-1], mn[pa[u][i-1]][i-1]+qs[u]-qs[pa[u][i-1]]);
    //for (int i=0; i<4; i++) cout<<u<<' '<<i<<' '<<mn[u][i]<<'\n';
    for (auto [x, y]:t[u]) 
    {
        if (dp[x])
        {
            ll dn=dp[x], res=mnd[u], tmp=u, vl=0;
            for (int i=kx-1; i>=0; i--) if (lvl[pa[tmp][i]]>=lvl[dn]) res=min(res, mn[tmp][i]+vl), vl+=qs[tmp]-qs[pa[tmp][i]], tmp=pa[tmp][i];
            ans[y]=res; 
        }
        else ans[y]=-1;
    }
    for (auto [v, w, i]:d[u])
    {
        if (v==p) continue;
        dp[i]=v;
        mn[v][0]=min(mnd[u]+w, (ll)1e18);
        dfs2(v, u);
        dp[i]=0;
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>s>>q>>e;
    for (int i=1; i<=n-1; i++) cin>>u>>v>>w, d[u].push_back({v, w, i}), d[v].push_back({u, w, i});
    for (int i=1; i<=n; i++) mnd[i]=1e18;
    for (int i=0; i<s; i++) cin>>x, pw[x]=1;
    for (int i=0; i<q; i++) cin>>x>>y, t[y].push_back({x, i});
    dfs(e, e);
    mn[e][0]=1e18;
    dfs2(e, e);
    for (int i=0; i<q; i++)
    {
        if (ans[i]==-1) cout<<"escaped\n";
        else if (ans[i]>=1e18) cout<<"oo\n";
        else cout<<ans[i]<<'\n';
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 3 ms 11064 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 3 ms 11064 KB Output is correct
5 Correct 2 ms 11072 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 10940 KB Output is correct
10 Correct 3 ms 11096 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 3 ms 11100 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 2 ms 11100 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 45280 KB Output is correct
2 Correct 142 ms 45396 KB Output is correct
3 Correct 143 ms 45440 KB Output is correct
4 Correct 147 ms 47804 KB Output is correct
5 Correct 127 ms 47996 KB Output is correct
6 Correct 146 ms 51540 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 3 ms 11064 KB Output is correct
5 Correct 2 ms 11072 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 10940 KB Output is correct
10 Correct 3 ms 11096 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 3 ms 11100 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 2 ms 11100 KB Output is correct
15 Correct 123 ms 45280 KB Output is correct
16 Correct 142 ms 45396 KB Output is correct
17 Correct 143 ms 45440 KB Output is correct
18 Correct 147 ms 47804 KB Output is correct
19 Correct 127 ms 47996 KB Output is correct
20 Correct 146 ms 51540 KB Output is correct
21 Correct 118 ms 48652 KB Output is correct
22 Correct 127 ms 48468 KB Output is correct
23 Correct 125 ms 48472 KB Output is correct
24 Correct 157 ms 51772 KB Output is correct
25 Correct 155 ms 55892 KB Output is correct
26 Correct 113 ms 48564 KB Output is correct
27 Correct 123 ms 48632 KB Output is correct
28 Correct 141 ms 48776 KB Output is correct
29 Correct 146 ms 50512 KB Output is correct
30 Correct 144 ms 53072 KB Output is correct
31 Correct 119 ms 48644 KB Output is correct
32 Correct 127 ms 48724 KB Output is correct
33 Correct 134 ms 48844 KB Output is correct
34 Correct 147 ms 51344 KB Output is correct
35 Correct 160 ms 55888 KB Output is correct
36 Correct 130 ms 51568 KB Output is correct