제출 #825680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825680		Shreyan_Paliwal	Valley (BOI19_valley)	C++17	100 / 100	412 ms	51916 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 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 bl(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] && bl(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] = 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++;
}

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

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

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);
}

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, bld[nd][i]);
            nd = bl[nd][i];
        }
    }
    ans = min(ans, bld[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);
    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 forb_id, cur_vertex;
        cin >> forb_id >> cur_vertex;

        if (!is_parent(cur_vertex, edges[forb_id - 1].first)) {
           cout << "escaped" << endl;
           continue;
        }

        int cur_h = dist[cur_vertex];
        
        int diff = dpth[cur_vertex] - dpth[edges[forb_id - 1].first];
        int ans = INF;
        for (int i = 20 - 1; i >= 0; i--) {
            if (diff & 1 << i) {
                ans = min(ans, bld[cur_vertex][i]);
                cur_vertex = bl[cur_vertex][i];
            }
        }
        ans = min(ans, bld[cur_vertex][0]);

        if (ans != INF) {
            ans += cur_h;
        }

        if (ans == INF) {
            cout << "oo" << '\n';
        } else {
            cout << ans << '\n';
        }
    }
}

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