oj.uz

Submission #825666

# Submission time Handle Problem Language Result Execution time Memory
825666 2023-08-15T06:58:32 Z Shreyan_Paliwal Valley (BOI19_valley) C++17
100 / 100
 362 ms 51892 KB 
// // #pragma GCC optimize("Ofast")
// // #include <bits/stdc++.h>
// // using namespace std;

// // #define int long long

// // const int maxn = 100000;
// // const int INF = 2000000000;

// // int n, s, q, e; // nodes, numshops, numqueries, valleynode
// // vector<pair<int,int>> adj[maxn];
// // pair<int,int> edges[maxn];
// // int shop[maxn]; // is shop?
// // int closest[maxn]; // closest shop in subtree

// // int dist[maxn]; // distance to e, set


// // int dpth[maxn]; // depth from e, set
// // int bl[maxn][20]; // set
// // int bld[maxn][20]; // array[nd] = - 2 * dist[nd] + min(dist[shop]) for shop in subtree[dist]


// // void dfs(int nd, int par, int pardist, int d) {
// //     // set depth
// //     dpth[nd] = d;

// //     // set binary lifting
// //     bl[nd][0] = par;
// //     for (int i = 1; i < 20; i++) bl[nd][i] = bl[bl[nd][i-1]][i-1];

// //     // recurse dfs, set distance from e
// //     for (auto i : adj[nd])
// //         if (i.first != par) {
// //             dist[i.first] = dist[nd] + i.second;    
// //             dfs(i.first, nd, i.second, d+1);
// //         }
    
// //     // init closest shop in subtree
// //     closest[nd] = shop[nd] ? 0 : INF;   
// //     for (auto i : adj[nd])
// //         if (i.first != par)
// //             closest[nd] = min(closest[nd], i.second + closest[i.first]);

// //     return;
// // }

// // void dfs_bld(int nd) {
// //     if (closest[nd] == INF) bld[nd][0] = INF;
// //     else bld[nd][0] = -dist[nd] + closest[nd];
// //     for (int i = 1; i < 20; i++) bld[nd][i] = min(bld[nd][i-1], bld[bl[nd][i-1]][i-1]);

// //     for (auto i : adj[nd])
// //         if (i.first != bl[nd][0])
// //             dfs_bld(i.first);
// // }

// // inline int jmp(int nd, int k) {
// //     for (int i = 19; i >= 0; i--) if ((k >> i) & 1) nd = bl[nd][i];
// //     return nd;
// // }

// // inline bool on_path(int nd, int nd2) {
// //     // checking if nd2 is on nd's path to e
// //     return (dpth[nd] >= dpth[nd2] && jmp(nd, dpth[nd] - dpth[nd2]) == nd2);
// // }

// // void solve() {
// //     cin >> n >> s >> q >> e; e--;
// //     for (int i = 0; i < n-1; i++) {
// //         int c; cin >> edges[i].first >> edges[i].second >> c;
// //         edges[i].first--, edges[i].second--;
// //         adj[edges[i].first].push_back({edges[i].second, c});
// //         adj[edges[i].second].push_back({edges[i].first, c});
// //     }

// //     for (int i = 0; i < s; i++) { int a; cin >> a; a--; shop[a] = 1; }

// //     dfs(e, e, 0, 0);
// //     dfs_bld(e);

// //     for (int i = 0; i < q; i++) {
// //         // a is a removed, b is b to find
// //         int a, b; cin >> a >> b; a--, b--;

// //         if (dpth[edges[a].first] < dpth[edges[a].second]) 
// //             swap(edges[a].first, edges[a].second);

// //         // check if escape possible
// //         if (!on_path(b, edges[a].first)) {
// //             cout << "escaped" << endl;
// //             continue;
// //         }

// //         // not possible, so search
// //         int val = INF;
// //         int B = b;
// //         for (int i = 19; i >= 0; i--) 
// //             if (((dpth[edges[a].first] - dpth[b] + 1) >> i) & 1)
// //                 val = min(val, bld[b][i]), 
// //                 b = bl[b][i];

// //         if (val == INF) {
// //             cout << "oo" << endl;
// //             continue;
// //         }

// //         cout << val + dist[B] << endl;
// //         continue;
// //     }

// // }

// // signed main() {
// //     cin.tie(nullptr) -> ios::sync_with_stdio(false);
// //     // freopen("main.in", "r", stdin);
// //     int t; 
// //     // cin >> t;
// //     t=1;
// //     while(t--) solve();
// //     return 0;
// // }

// #include <bits/stdc++.h>
// using namespace std;

// #define int long long

// const int maxn = 200000;
// const int INF = 1ll << 60;

// int n, s, q, e;

// vector<pair<int,int>> adj[maxn];
// pair<int,int> edges[maxn];

// int dist[maxn];
// int dpth[maxn];
// int closest[maxn];
// int shop[maxn];

// int bl[maxn][20];
// int bld[maxn][20];

// int st[maxn], en[maxn], cur = 0;

// void dfs(int nd, int par, int d) {
//     st[nd] = cur++;
//     dist[nd] = dist[par] + d;
//     dpth[nd] = dpth[par] + 1;

//     for (auto i : adj[nd])
//         if (i.first != par)
//             dfs(i.first, nd, i.second);

//     closest[nd] = (shop[nd] ? dist[nd] : INF);
//     for (auto i : adj[nd])
//         if (i.first != par && closest[i.first] != INF)
//             closest[nd] = min(closest[nd], closest[i.first]);
    
//     en[nd] = cur++;
// }

// void dfs_bl(int nd, int par) {
//     bl[nd][0] = par;
//     bld[nd][0] = (closest[nd] == INF ? INF : closest[nd] - 2 * dist[nd]);

//     for (int i = 1; i < 20; i++) bl[nd][i] = bl[bl[nd][i-1]][i-1];
//     for (int i = 1; i < 20; i++) bld[nd][i] = min(bld[nd][i-1], bld[bl[nd][i-1]][i-1]);

//     for (auto i : adj[nd])
//         if (i.first != par)
//             dfs_bl(i.first, nd);
// }

// signed main() {
//     // freopen("main.in", "r", stdin);

//     cin >> n >> s >> q >> e; e--;

//     for (int i = 0; i < n-1; i++) {
//         int a, b, c; cin >> a >> b >> c; a--, b--;
//         adj[a].push_back({b, c});
//         adj[b].push_back({a, c});
//         edges[i] = make_pair(b, c);
//     }

//     for (int i = 0; i < s; i++) {
//         int a; cin >> a; a--;
//         shop[a] = 1;
//     }

//     dfs(e, e, 0);
//     dfs_bl(e, e);

//     for (int i = 0; i < n-1; i++)
//         if (dpth[edges[i].first] < dpth[edges[i].second])
//             swap(edges[i].first, edges[i].second);

//     for (int i = 0; i < q; i++) {
//         int a, b; cin >> a >> b; a--, b--;
//         // if (dpth[edges[a].first] < dpth[edges[a].second]) swap(edges[a].first, edges[a].second);

//         // can escape?
//         if (!(st[edges[a].first] <= st[b] && en[b] <= en[edges[a].first])) {
//             cout << "escaped" << endl;
//             continue;
//         }

//         int cost = INF;
//         int nd = b;
//         for (int i = 19; i >= 0; i--)
//             if (((dpth[b] - dpth[edges[a].first]) >> i) & 1)
//                 cost = min(cost, bld[nd][i]), 
//                 nd = bl[nd][i];
//         cost = min(cost, bld[nd][0]);

//         if (cost == INF) { cout << "oo" << endl; continue; }

//         cout << cost + dist[b] << endl;
//         continue;
//     }

//     return 0;
// }


#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn = 200005;
const int inf = 1LL << 60;

int n, s, q, e;
vector<pair<int, int>> adj[maxn];
pair<int,int> edges[maxn];

int dist[maxn];
int dpth[maxn];

int closest[maxn];
bool shop[maxn];
int st[maxn], en[maxn], cur = 0;

void dfs(int nd, int par, int d) {
    st[nd] = ++cur;
    dist[nd] = d;
    dpth[nd] = dpth[par] + 1;
    
    for (auto i : adj[nd])
        if (i.first != par)
            dfs(i.first, nd, d + i.second);

    closest[nd] = (shop[nd] ? dist[nd] : inf);
    for (auto i : adj[nd])
        if (i.first != par)
            closest[nd] = min(closest[nd], closest[i.first]);

    en[nd] = cur;
}

bool is_parent (int u, int par) {
    return st[par] <= st[u] && en[u] <= en[par];
}

int jmp [maxn][20];
int ans_jmp [maxn][20];

void build_jmp (int nd, int par) {
    jmp[nd][0] = par;
    if (closest[nd] == inf) {
        ans_jmp[nd][0] = inf;
    } else {
        ans_jmp[nd][0] = closest[nd] - 2 * dist[nd];
    }

    for (int i = 1; i < 20; i++) {
        jmp[nd][i] = jmp[jmp[nd][i - 1]][i - 1];
        ans_jmp[nd][i] = min(ans_jmp[nd][i - 1], ans_jmp[jmp[nd][i - 1]][i - 1]);
    }

    for (pair<int, int> nxt : adj[nd]) {
        if (nxt.first != par) {
            build_jmp(nxt.first, nd);
        }
    }
}

int query (int nd, int forb) {
    if (!is_parent(nd, forb)) {
        return -1;
    }

    int cur_h = dist[nd];
    
    int diff = dpth[nd] - dpth[forb];
    int ans = inf;
    for (int i = 20 - 1; i >= 0; i--) {
        if (diff & 1 << i) {
            ans = min(ans, ans_jmp[nd][i]);
            nd = jmp[nd][i];
        }
    }
    ans = min(ans, ans_jmp[nd][0]);

    if (ans != inf) {
        ans += cur_h;
    }
    
    return ans;
}

signed main () {
    cin >> n >> s >> q >> e;

    for (int i = 0; i < n - 1; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(b, c));
        adj[b].push_back(make_pair(a, c));
        edges[i] = make_pair(a, b);
    }



    for (int i = 0; i < s; i++) {
        int x;
        cin >> x;
        shop[x] = true;
    }

    dfs(e, e, 0);
    build_jmp(e, e);
    
    for (int i = 0; i < n - 1; i++) {
        if (dpth[edges[i].first] < dpth[edges[i].second]) {
            swap(edges[i].first, edges[i].second);
        }
    }
    
    for (int i = 0; i < q; i++) {
        int forb_id, cur_vertex;
        cin >> forb_id >> cur_vertex;

        int ans = query(cur_vertex, edges[forb_id - 1].first);
        if (ans == -1) {
            cout << "escaped" << '\n';
        } else if (ans == inf) {
            cout << "oo" << '\n';
        } else {
            cout << ans << '\n';
        }
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5076 KB Output is correct
2 Correct 15 ms 5152 KB Output is correct
3 Correct 16 ms 5156 KB Output is correct
4 Correct 16 ms 5160 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5076 KB Output is correct
2 Correct 15 ms 5152 KB Output is correct
3 Correct 16 ms 5156 KB Output is correct
4 Correct 16 ms 5160 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5416 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 4 ms 5432 KB Output is correct
9 Correct 5 ms 5460 KB Output is correct
10 Correct 5 ms 5460 KB Output is correct
11 Correct 5 ms 5460 KB Output is correct
12 Correct 5 ms 5460 KB Output is correct
13 Correct 5 ms 5460 KB Output is correct
14 Correct 5 ms 5416 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 47596 KB Output is correct
2 Correct 322 ms 47452 KB Output is correct
3 Correct 330 ms 47832 KB Output is correct
4 Correct 362 ms 49324 KB Output is correct
5 Correct 343 ms 49376 KB Output is correct
6 Correct 362 ms 51020 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5076 KB Output is correct
2 Correct 15 ms 5152 KB Output is correct
3 Correct 16 ms 5156 KB Output is correct
4 Correct 16 ms 5160 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5416 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 4 ms 5432 KB Output is correct
9 Correct 5 ms 5460 KB Output is correct
10 Correct 5 ms 5460 KB Output is correct
11 Correct 5 ms 5460 KB Output is correct
12 Correct 5 ms 5460 KB Output is correct
13 Correct 5 ms 5460 KB Output is correct
14 Correct 5 ms 5416 KB Output is correct
15 Correct 322 ms 47596 KB Output is correct
16 Correct 322 ms 47452 KB Output is correct
17 Correct 330 ms 47832 KB Output is correct
18 Correct 362 ms 49324 KB Output is correct
19 Correct 343 ms 49376 KB Output is correct
20 Correct 362 ms 51020 KB Output is correct
21 Correct 305 ms 47652 KB Output is correct
22 Correct 322 ms 47488 KB Output is correct
23 Correct 304 ms 47664 KB Output is correct
24 Correct 349 ms 49356 KB Output is correct
25 Correct 333 ms 51892 KB Output is correct
26 Correct 294 ms 47752 KB Output is correct
27 Correct 303 ms 47484 KB Output is correct
28 Correct 321 ms 47736 KB Output is correct
29 Correct 349 ms 48936 KB Output is correct
30 Correct 361 ms 50344 KB Output is correct
31 Correct 289 ms 47764 KB Output is correct
32 Correct 298 ms 47556 KB Output is correct
33 Correct 317 ms 47860 KB Output is correct
34 Correct 357 ms 49344 KB Output is correct
35 Correct 337 ms 51756 KB Output is correct
36 Correct 319 ms 49816 KB Output is correct