Submission #933665

#	Time	Username	Problem	Language	Result	Execution time	Memory
933665		Whisper	Valley (BOI19_valley)	C++17	100 / 100	168 ms	69204 KiB

valley

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define pii pair<int , int>
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 2e5 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int numNode, numShop, numQuery, Exit;

int tin[MAX], tout[MAX], dep[MAX], d[MAX], hasShop[MAX];
int dis[MAX][23], up[MAX][23];
int cnt = 0;
int dp[MAX];

vector<pair<int, int>> adj[MAX];
void dfs(int u, int p = -1){
    tin[u] = ++cnt;
    dp[u] = (hasShop[u] ? 0 : LINF);
    for (pair<int, int> &x : adj[u]){
        int v = x.first, w = x.second;
        if(v ^ p){
            d[v] = d[u] + w;
            dep[v] = dep[u] + 1;
            up[v][0] = u;
            dfs(v, u);
            minimize(dp[u], dp[v] + w);
        }
    }
    tout[u] = cnt;
    for (int i = 1; i <= 21; ++i) dis[u][i] = LINF;
}

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

void pre_dfs(int u, int p = -1){
    for (pair<int, int>&x : adj[u]){
        int v = x.first, w = x.second;
        if (v ^ p){
            dis[v][0] = dp[u] - d[u];
            for (int i = 1; i <= 21; ++i){
                up[v][i] = up[up[v][i - 1]][i - 1];
                dis[v][i] = min(dis[v][i - 1], dis[up[v][i - 1]][i - 1]);
            }
            pre_dfs(v, u);
        }
    }
}

int query(int u, int v){
    int dist = dep[u] - dep[v];
    int res = dp[u] - d[u];
    for (int i = 0; MASK(i) <= dist; ++i){
        if (BIT(dist, i)){
            minimize(res, dis[u][i]); u = up[u][i];
        }
    }
    return res;
}
void Whisper(){
    cin >> numNode >> numShop >> numQuery >> Exit;

    vector<array<int, 3>> edge(numNode + 1);
    for (int i = 1; i < numNode; ++i){
        int u, v, w; cin >> u >> v >> w;
        edge[i] = {u, v, w};
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    for (int i = 1; i <= numShop; ++i){
        int x; cin >> x;
        hasShop[x] = 1;
    }
    dfs(Exit); pre_dfs(Exit);
    for (int t = 1; t <= numQuery; ++t){
        int i, r; cin >> i >> r;
        int u = edge[i][0], v = edge[i][1];
        if(dep[u] < dep[v]) swap(u, v);
        if (!is_ancestor(u, r)) cout << "escaped\n";
        else{
            int ans = query(r, u) + d[r];
            if (ans >= LINF) cout << "oo\n";
            else cout << ans << '\n';
        }
    }
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Compilation message (stderr)

valley.cpp: In function 'void pre_dfs(long long int, long long int)':
valley.cpp:77:26: warning: unused variable 'w' [-Wunused-variable]
   77 |         int v = x.first, w = x.second;
      |                          ^

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