oj.uz

답안 #709328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709328 2023-03-13T11:41:00 Z lukameladze Valley (BOI19_valley) C++14
100 / 100
 271 ms 58132 KB 
# 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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7568 KB Output is correct
2 Correct 7 ms 7532 KB Output is correct
3 Correct 9 ms 7636 KB Output is correct
4 Correct 6 ms 7608 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7568 KB Output is correct
2 Correct 7 ms 7532 KB Output is correct
3 Correct 9 ms 7636 KB Output is correct
4 Correct 6 ms 7608 KB Output is correct
5 Correct 6 ms 7908 KB Output is correct
6 Correct 6 ms 7904 KB Output is correct
7 Correct 6 ms 7892 KB Output is correct
8 Correct 6 ms 7892 KB Output is correct
9 Correct 7 ms 7892 KB Output is correct
10 Correct 7 ms 7916 KB Output is correct
11 Correct 6 ms 7908 KB Output is correct
12 Correct 6 ms 7912 KB Output is correct
13 Correct 5 ms 7916 KB Output is correct
14 Correct 7 ms 7892 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 54608 KB Output is correct
2 Correct 201 ms 54484 KB Output is correct
3 Correct 217 ms 54604 KB Output is correct
4 Correct 243 ms 56128 KB Output is correct
5 Correct 214 ms 56296 KB Output is correct
6 Correct 271 ms 57920 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7568 KB Output is correct
2 Correct 7 ms 7532 KB Output is correct
3 Correct 9 ms 7636 KB Output is correct
4 Correct 6 ms 7608 KB Output is correct
5 Correct 6 ms 7908 KB Output is correct
6 Correct 6 ms 7904 KB Output is correct
7 Correct 6 ms 7892 KB Output is correct
8 Correct 6 ms 7892 KB Output is correct
9 Correct 7 ms 7892 KB Output is correct
10 Correct 7 ms 7916 KB Output is correct
11 Correct 6 ms 7908 KB Output is correct
12 Correct 6 ms 7912 KB Output is correct
13 Correct 5 ms 7916 KB Output is correct
14 Correct 7 ms 7892 KB Output is correct
15 Correct 203 ms 54608 KB Output is correct
16 Correct 201 ms 54484 KB Output is correct
17 Correct 217 ms 54604 KB Output is correct
18 Correct 243 ms 56128 KB Output is correct
19 Correct 214 ms 56296 KB Output is correct
20 Correct 271 ms 57920 KB Output is correct
21 Correct 158 ms 53308 KB Output is correct
22 Correct 148 ms 53132 KB Output is correct
23 Correct 156 ms 53320 KB Output is correct
24 Correct 209 ms 55004 KB Output is correct
25 Correct 207 ms 57492 KB Output is correct
26 Correct 137 ms 53608 KB Output is correct
27 Correct 156 ms 53356 KB Output is correct
28 Correct 168 ms 53596 KB Output is correct
29 Correct 174 ms 54868 KB Output is correct
30 Correct 214 ms 56268 KB Output is correct
31 Correct 142 ms 54144 KB Output is correct
32 Correct 142 ms 53984 KB Output is correct
33 Correct 155 ms 54312 KB Output is correct
34 Correct 218 ms 55980 KB Output is correct
35 Correct 208 ms 58132 KB Output is correct
36 Correct 195 ms 55728 KB Output is correct