oj.uz

답안 #933665

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933665 2024-02-26T04:19:59 Z Whisper Valley (BOI19_valley) C++17
100 / 100
 168 ms 69204 KB 
#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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 5 ms 13204 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 5 ms 13204 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14996 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 4 ms 14940 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 4 ms 14940 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 60852 KB Output is correct
2 Correct 131 ms 59660 KB Output is correct
3 Correct 136 ms 59984 KB Output is correct
4 Correct 155 ms 61752 KB Output is correct
5 Correct 139 ms 61836 KB Output is correct
6 Correct 165 ms 64168 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 5 ms 13204 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14996 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 4 ms 14940 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 4 ms 14940 KB Output is correct
15 Correct 116 ms 60852 KB Output is correct
16 Correct 131 ms 59660 KB Output is correct
17 Correct 136 ms 59984 KB Output is correct
18 Correct 155 ms 61752 KB Output is correct
19 Correct 139 ms 61836 KB Output is correct
20 Correct 165 ms 64168 KB Output is correct
21 Correct 118 ms 63168 KB Output is correct
22 Correct 135 ms 63124 KB Output is correct
23 Correct 134 ms 63356 KB Output is correct
24 Correct 159 ms 65464 KB Output is correct
25 Correct 158 ms 68440 KB Output is correct
26 Correct 114 ms 63316 KB Output is correct
27 Correct 120 ms 63068 KB Output is correct
28 Correct 130 ms 63200 KB Output is correct
29 Correct 153 ms 64848 KB Output is correct
30 Correct 160 ms 66388 KB Output is correct
31 Correct 110 ms 63316 KB Output is correct
32 Correct 129 ms 63252 KB Output is correct
33 Correct 131 ms 63536 KB Output is correct
34 Correct 168 ms 65408 KB Output is correct
35 Correct 163 ms 69204 KB Output is correct
36 Correct 146 ms 65364 KB Output is correct