Submission #709328

#	Time	Username	Problem	Language	Result	Execution time	Memory
709328		lukameladze	Valley (BOI19_valley)	C++14	100 / 100	271 ms	58132 KiB

valley

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, inf = 1e12;
int t,n,a[N], dp[N], dep[N],lv[N],tin,in[N],out[N], fix[N],m,q,rt,ed_a[N],ed_b[N];
vector <pii> v[N];
pii par[N][20];
void dfs(int a, int p) {
    if (!fix[a]) dp[a] = inf;
    else dp[a] = -lv[a];
   
    dep[a] = dep[p] + 1;
    tin++;
    in[a] = tin;
    
    for (pii sth : v[a]) {
        int to = sth.f; int c = sth.s;
        if (to == p) continue;
        lv[to] = lv[a] + c;
        dfs(to, a);
        if (dp[to] != inf)
        dp[a] = min(dp[a], dp[to] + 2 * (lv[to] - lv[a]));
    }
    out[a] = tin;
}
void dfs1(int a, int p) {
    
    par[a][0] = {p, dp[a]};
    for (int i = 1; i <= 18; i++) {
        if (par[a][i - 1].f) {
            par[a][i].f = par[par[a][i - 1].f][i - 1].f;
            par[a][i].s = min(par[a][i - 1].s, par[par[a][i - 1].f][i - 1].s);
        }
    }
    for (pii sth : v[a]) {
        int to = sth.f; int c = sth.s;
        if (to == p) continue;
        dfs1(to, a);
    }
}
int upper(int a, int b) {
    return (in[a] <= in[b] && out[a] >= out[b]);
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q>>rt;
    for (int i = 1; i <= n - 1; i++) {
        int a, b, c; cin>>a>>b>>c;
        ed_a[i] = a; ed_b[i] = b;
        v[a].pb({b, c});
        v[b].pb({a, c}); 
    }
    for (int i = 1; i <= m; i++) {
        int a; cin>>a;
        fix[a] = 1;
    }
    dfs(rt, 0);
    dfs1(rt, 0);
    for (int i = 1; i <= q; i++) {
        int idx, vert, a, b;
        cin>>idx>>vert;
        a = ed_a[idx]; b = ed_b[idx];
        if (lv[a] < lv[b]) swap(a, b);
        if(!upper(a, vert)) {
            cout<<"escaped\n"; continue;
        }
        int dif = dep[vert] - dep[a] + 1;
        int ans = inf, cur = vert;
        for (int i = 0; i <= 18; i++) {
            if ((1<<i)&dif) {
                ans = min(ans, par[cur][i].s);
                cur = par[cur][i].f;
            }
        }
        if (ans == inf) cout<<"oo\n";
        else cout<<ans + lv[vert]<<"\n";
    }
}

Compilation message (stderr)

valley.cpp: In function 'void dfs1(long long int, long long int)':
valley.cpp:40:29: warning: unused variable 'c' [-Wunused-variable]
   40 |         int to = sth.f; int c = sth.s;
      |                             ^
valley.cpp: At global scope:
valley.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~

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