Submission #825614

#	Time	Username	Problem	Language	Result	Execution time	Memory
825614		Shreyan_Paliwal	Valley (BOI19_valley)	C++17	0 / 100	180 ms	90488 KiB

valley

// #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 root, set


// int dpth[maxn]; // depth from root, 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 root
//     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 root
//     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 = 100000;
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 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] = (closest[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--;
        closest[a] = 1;
    }

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

    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] + 1) >> i) & 1)
                cost = min(cost, bld[nd][i]), 
                nd = bl[nd][i];
        
        if (cost == INF) { cout << "oo" << endl; continue; }

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

    return 0;
}

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