oj.uz

Submission #1097339

# Submission time Handle Problem Language Result Execution time Memory
1097339 2024-10-07T01:22:45 Z Phuoc Valley (BOI19_valley) C++14
23 / 100
 129 ms 38636 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define el '\n'

template <class T1, class T2>
    bool maximize(T1 &a, T2 b) {
        if(a < b) {a = b; return true;} return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b) {
        if(a > b) {a = b; return true;} return false;
    }

const ll MOD = (ll)1e9 + 7;
const int oo = (int)1e9 + 10;
const ll INF = (ll)1e18 + 9LL;

template <class T1, class T2>
    void add (T1 &a, T2 b) {
        a += b;
        if(a >= MOD) a -= MOD;
    }

const int N = 100100;
const int LOG = 18;

int nVillage, nFarm, styn, nQuery;
vector <pair<int, ll> > adj [N];
bool isFarm[N];
pair <int, int> queries [N];

struct edge {
    int u, v; ll c;
    edge (int _u = 0, int _v = 0, ll _c = 0) {
        u = _u; v = _v; c = _c;
    }
} edges[N];

void init (void) {
    cin >> nVillage >> nFarm >> nQuery >> styn;
    for (int i = 1; i < nVillage; i++) {
        int u, v; ll c; cin >> u >> v >> c;
        adj[u].push_back(make_pair(v, c));
        adj[v].push_back(make_pair(u, c));
        edges[i] = edge (u, v, c);
    }
    for (int i = 1; i <= nFarm; i++) {
        int x; cin >> x; isFarm[x] = true;
    }
}

int fin[N], fout[N], dep[N], par[N][LOG];
ll dist[N], dp[N], minVal[N][LOG], val[N];
bool have_farm_in[N];
int tgDfs = 0;

void dfs (int u, int p) {
    fin[u] = ++tgDfs;
    have_farm_in[u] = isFarm[u];
    for (auto x : adj[u]) {
        int v = x.fi;
        if(v == p) continue;
        dep[v] = dep[u] + 1;
        dist[v] = dist[u] + x.se;
        par[v][0] = u;
        dfs (v, u);
        if(have_farm_in[v]) have_farm_in[u] = true;
    }
    fout[u] = tgDfs;
}

void calc (int u, int p) {
    dp[u] = isFarm[u] ? 0 : INF;
    for (auto x : adj[u]) {
        int v = x.fi;
        if(v == p) continue;
        calc(v, u);
        minimize(dp[u], dp[v] + x.se);
    }
}

void build_val (int u, int p) {
    // if(p == 0) minVal[u][0] = dp[u] - dist[u];
    // else minVal[u][0] = min(dp[u] - dist[u], dp[p] - dist[p]);
    // for (int i = 1; i < LOG; i++) {
    //     minVal[u][i] = min(minVal[u][i - 1], minVal[par[u][i - 1]][i - 1]);
    // }    
    for (auto x : adj[u]) {
        int v = x.fi;
        if(v == p) continue;
        minVal[v][0] = min(dp[u] - dist[u], dp[v] - dist[v]);
        build_val(v, u);
    }
}

int getMin (int u, int diff) {
    int ans = oo;
    for (int i = 0; i < LOG; i++) {
        if(BIT(diff, i)) {
            minimize(ans, minVal[u][i]);
            u = par[u][i];
        }
    }
    return ans;
}

void solve (void) {
    dfs (styn, 0);
    calc (styn, 0);
    for (int j = 1; j < LOG; j++) for(int i = 1; i <= nVillage; i++) par[i][j] = par[par[i][j - 1]][j - 1];

    memset(minVal, oo, sizeof minVal); 
    // memset(dp, oo, sizeof dp);
    build_val(styn, 0);
    for (int j = 1; j < LOG; j++) for (int i = 1; i <= nVillage; i++) minVal[i][j] = min(minVal[i][j - 1], minVal[par[i][j - 1]][j - 1]);

    for (int lmao = 1; lmao <= nQuery; lmao++) {
        int ban, node; cin >> ban >> node;
        edge e = edges[ban];
        int u = e.u, v = e.v;
        if(dep[v] < dep[u]) swap(u, v); 
        if(!(fin[node] >= fin[v] && fin[node] <= fout[v])) {
            cout << "escaped" << el;
        }
        else {
            if(!have_farm_in[v]) {
                cout << "oo" << el;
                continue;
            }
            ll ans = INF;
            if(have_farm_in[node]) minimize(ans, dp[node]);
            int diff = dep[node] - dep[v];
            minimize(ans, getMin(node, diff) + dist[node]);
            cout << ans << el;
        }
    }
}

int main (void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int ntest = 1;

    while (ntest--) {
        init();
        solve();
    }
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18524 KB Output is correct
2 Incorrect 8 ms 18524 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18524 KB Output is correct
2 Incorrect 8 ms 18524 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 34128 KB Output is correct
2 Correct 102 ms 33924 KB Output is correct
3 Correct 113 ms 34132 KB Output is correct
4 Correct 119 ms 36124 KB Output is correct
5 Correct 111 ms 36180 KB Output is correct
6 Correct 129 ms 38636 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18524 KB Output is correct
2 Incorrect 8 ms 18524 KB Output isn't correct
3 Halted 0 ms 0 KB -