oj.uz

답안 #286729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
286729 2020-08-30T19:56:14 Z caoash Valley (BOI19_valley) C++14
100 / 100
 368 ms 61932 KB 
#include <bits/stdc++.h> 
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

const int MX = 100005;
const ll INF = (ll) 1e18;

vector<pi> adj[MX]; ll dep[MX], dp[MX]; int tin[MX], tout[MX]; bool village[MX];

template<int SZ> struct LCA{
    int depth[SZ]; int p[SZ][33]; vector<int> adj[SZ]; ll p_min[SZ][33];
    void addEdge(int u, int v){
      adj[u].push_back(v); adj[v].push_back(u);
    }
    void dfs(int v, int par){
        for(int to : adj[v]){
          if(to != par){
            p[to][0] = v; depth[to] = depth[v] + 1;
            dfs(to, v);
          }
        }
    }
    void precomp(int root, ll dp[MX]) {
        for (int i = 0; i < SZ; i++) {
            for (int j = 0; j < 32; j++) {
                p[i][j] = -1;
                p_min[i][j] = INT_MAX;
            }
            p_min[i][0] = dp[i];
        }
        p[root][0] = root;
        dfs(root, -1);
        for (int j = 1; j < 32; j++) {
            for (int i = 0; i < SZ; i++) {
                if (p[i][j - 1] == -1) {
                    p[i][j] = -1;
                    p_min[i][j] = INT_MAX;
                } else {
                    p[i][j] = p[p[i][j - 1]][j - 1];
                    p_min[i][j] = min(p_min[i][j - 1], p_min[p[i][j - 1]][j - 1]);
                }
            }
        }
    }
    int gdep(int v) {
        return depth[v];
    }
    int query(int a, int b) {
        if (depth[a] > depth[b]) {
            swap(a, b);
        }
        int lift = depth[b] - depth[a];
        for (int j = 31; j >= 0; j--) {
            if (lift & (1 << j)) {
                b = p[b][j];
            }
        }
        for (int j = 31; j >= 0; j--) {
            if (p[a][j] != p[b][j]) {
                a = p[a][j];
                b = p[b][j];
            }
        }
        return (a == b) ? a : p[a][0];
    }
    ll query2(int a, int b) {
        int curr = a;
        ll ans = INF;
        for(int i = 31; i >= 0; i--){
            if(b & (1 << i)) {
                ans = min(p_min[curr][i], ans);
                curr = p[curr][i];
            }
        }
        assert(curr != -1);
        return ans;
    }
};

LCA<MX> anc; 

int cnt = 0;

void dfs(int v, int p) {
    tin[v] = cnt++;
    for (pi to : adj[v]) {
        if (to.f != p) {
            dep[to.f] = dep[v] + to.s;
            dfs(to.f, v);
        }
    }
    tout[v] = cnt++;
}

void dfs2(int v, int p) {
    if (village[v]) {
        dp[v] = dep[v];
        // cerr << "v: " << v << " " << dep[v] << "\n";
    }
    for (pi to : adj[v]) {
        if (to.f != p) {
            dfs2(to.f, v);
            dp[v] = min(dp[v], dp[to.f]);
        }
    }
} 

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

vector<pi> ed;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, s, q, e; cin >> n >> s >> q >> e;
    e--;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        adj[u].pb(mp(v, w)), adj[v].pb(mp(u, w));
        anc.addEdge(u, v);
        ed.pb(mp(u, v));
    }
    for (int i = 0; i < s; i++) {
        int x; cin >> x; 
        x--;
        village[x] = true;
    }
    dfs(e, -1);
    for (int i = 0; i < n; i++) dp[i] = INF;
    dfs2(e, -1);
    /*
    cerr << "DP: " << '\n';
    for (int i = 0; i < n; i++) {
        cerr << "i, dp[i]: " << i << " " << dp[i] << "\n";
    }
    */
    for (int i = 0; i < n; i++) if(dp[i] != INF) dp[i] -= 2 * dep[i];
    anc.precomp(e, dp);
    for (int i = 0; i < q; i++) {
        int ind, r; cin >> ind >> r;
        ind--, r--;
        pi curr = ed[ind];
        if (dep[curr.s] < dep[curr.f]) swap(curr.f, curr.s);
        // cout << "curr.s, r: " << curr.s + 1 << " " << r + 1 << '\n';
        if (is_anc(curr.s, r)) {
            int dist = anc.gdep(r) - anc.gdep(curr.f);
            // cout << dist << '\n';
            ll ret = anc.query2(r, dist);
            if (ret == INF) {
                cout << "oo" << '\n';
            }
            else {
                ret += dep[r];
                cout << ret << '\n';
            }
        }
        else {
            cout << "escaped" << '\n';
        }
    }
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 43896 KB Output is correct
2 Correct 92 ms 44024 KB Output is correct
3 Correct 93 ms 43896 KB Output is correct
4 Correct 92 ms 44012 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 43896 KB Output is correct
2 Correct 92 ms 44024 KB Output is correct
3 Correct 93 ms 43896 KB Output is correct
4 Correct 92 ms 44012 KB Output is correct
5 Correct 90 ms 44024 KB Output is correct
6 Correct 89 ms 44024 KB Output is correct
7 Correct 90 ms 44000 KB Output is correct
8 Correct 89 ms 44012 KB Output is correct
9 Correct 90 ms 43896 KB Output is correct
10 Correct 92 ms 43896 KB Output is correct
11 Correct 90 ms 44000 KB Output is correct
12 Correct 91 ms 44024 KB Output is correct
13 Correct 91 ms 44024 KB Output is correct
14 Correct 91 ms 44024 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 55528 KB Output is correct
2 Correct 310 ms 58860 KB Output is correct
3 Correct 327 ms 58604 KB Output is correct
4 Correct 345 ms 60012 KB Output is correct
5 Correct 323 ms 60140 KB Output is correct
6 Correct 368 ms 61612 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 43896 KB Output is correct
2 Correct 92 ms 44024 KB Output is correct
3 Correct 93 ms 43896 KB Output is correct
4 Correct 92 ms 44012 KB Output is correct
5 Correct 90 ms 44024 KB Output is correct
6 Correct 89 ms 44024 KB Output is correct
7 Correct 90 ms 44000 KB Output is correct
8 Correct 89 ms 44012 KB Output is correct
9 Correct 90 ms 43896 KB Output is correct
10 Correct 92 ms 43896 KB Output is correct
11 Correct 90 ms 44000 KB Output is correct
12 Correct 91 ms 44024 KB Output is correct
13 Correct 91 ms 44024 KB Output is correct
14 Correct 91 ms 44024 KB Output is correct
15 Correct 279 ms 55528 KB Output is correct
16 Correct 310 ms 58860 KB Output is correct
17 Correct 327 ms 58604 KB Output is correct
18 Correct 345 ms 60012 KB Output is correct
19 Correct 323 ms 60140 KB Output is correct
20 Correct 368 ms 61612 KB Output is correct
21 Correct 277 ms 58728 KB Output is correct
22 Correct 301 ms 58280 KB Output is correct
23 Correct 311 ms 58096 KB Output is correct
24 Correct 337 ms 59628 KB Output is correct
25 Correct 343 ms 61932 KB Output is correct
26 Correct 270 ms 58860 KB Output is correct
27 Correct 295 ms 58348 KB Output is correct
28 Correct 301 ms 58088 KB Output is correct
29 Correct 329 ms 59240 KB Output is correct
30 Correct 361 ms 60392 KB Output is correct
31 Correct 273 ms 58988 KB Output is correct
32 Correct 295 ms 58292 KB Output is correct
33 Correct 305 ms 58244 KB Output is correct
34 Correct 335 ms 59756 KB Output is correct
35 Correct 343 ms 61868 KB Output is correct
36 Correct 327 ms 59756 KB Output is correct