제출 #694093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
694093		vjudge1	Valley (BOI19_valley)	C++17	100 / 100	147 ms	37336 KiB

valley

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
using namespace std;

const int mxN = 1e5 + 5;
const int mod = 1e9 + 7;
const int lim = 17;
const ll oo = 1e18;

vector<pii> G[mxN];
bool shop[mxN];
int n, s, q, root, par[lim][mxN];
int tin[mxN], tout[mxN], timer;
vector<pii> edges;
ll dp[lim][mxN], dep[mxN];

void dfs(int v, int p) {
    tin[v] = ++timer;
    ll cur = oo;
    
    par[0][v] = p;
    if(shop[v])
        cur = dep[v];

    for(pii tmp : G[v]) {
        int u = tmp.ff, w = tmp.ss;
        if(u == p)
            continue;
        dep[u] = dep[v] + w;
        dfs(u, v);
        cur = min(cur, dp[0][u]);
    }
    dp[0][v] = cur;
    // cout << "0 " << v << ' ' << cur << endl;
    tout[v] = timer;
}

bool is_ancestor(int v, int u) {
    if(v == 0)
        return true;
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}

int find_lca(int v, int u) {
    if(is_ancestor(v, u))
        return v;
    if(is_ancestor(u, v))
        return u;

    for(int i = lim - 1; i >= 0; --i)
        if(!is_ancestor(par[i][v], u))
            v = par[i][v];

    return par[0][v];
}

void solve() {
    cin >> n >> s >> q >> root;
    for(int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].pb({v, w});
        G[v].pb({u, w});
        edges.pb({u, v});
    }
    for(int i = 1; i <= s; ++i) {
        int tmp; cin >> tmp;
        shop[tmp] = true;
    }
    dfs(root, 0);
    for(int i = 1; i <= n; ++i)
        if(dp[0][i] != oo)
            dp[0][i] -= 2 * dep[i];
    for(int i = 1; i < lim; ++i) {
        for(int j = 1; j <= n; ++j) {
            par[i][j] = par[i - 1][par[i - 1][j]];
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][par[i - 1][j]]);
            // cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    while(q--) {
        int idx, st;
        cin >> idx >> st;
        --idx;
        if(edges[idx].ss == par[0][edges[idx].ff])
            swap(edges[idx].ff, edges[idx].ss);
        if(is_ancestor(edges[idx].ss, st)) {
            ll res = oo;
            int ori_st = st;
            for(int i = lim - 1; i >= 0; --i) {
                if(is_ancestor(edges[idx].ss, par[i][st])) {
                    res = min(res, dp[i][st]);
                    // cout << i << " " << st << endl;
                    st = par[i][st];
                }
            }
            res = min(res, dp[0][st]);
            if(res == oo)
                cout << "oo\n";
            else
                cout << res + dep[ori_st] << "\n";
        }
        else
            cout << "escaped\n";
    }
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
    auto end = chrono::high_resolution_clock::now();
    cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
    cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

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