Submission #655149

#	Time	Username	Problem	Language	Result	Execution time	Memory
655149		HuyKoCoNy	Valley (BOI19_valley)	C++17	0 / 100	4 ms	5076 KiB

valley

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
// __builtin_popcount
// __builtin_ctz
#define int long long
#define pii pair<int, int>
#define duoble long double
#define endl '\n'
#define fi first
#define se second
#define mapa make_pair
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define o_ ordered_
#define ins insert
#define era erase
#define pqueue priority_queue
#define minele min_element
#define maxele max_element
#define lb lower_bound // >=
#define ub upper_bound // >
#define debug cout << "NO ERROR", exit(0)
#define FAST ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(v) v.begin(), v.end()
#define SZ(v) (int)v.size()
#define sqr(x) ((x) * (x))

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        return false;
    }

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

int Rand(const int &l, const int &r) {
    assert(l <= r);
    int sz = (r - l + 1);
    return l + rd() % sz;
}


const int MOD = 1e9 + 7; //998244353;
const int LOG = 18;
const int INF = 1e18 + 7;
const int d4x[4] = {-1, 1, 0, 0};
const int d4y[4] = {0, 0, 1, -1};
const char c4[4] = {'U', 'D', 'R', 'L'};
const int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};




// #define LENGTH 1000005
// #define NMOD 2
// #define BASE 256
// const int HashMod[] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277};

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define o_set tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update>
// *(s.find_by_order(2)) : 3rd element in the set i.e. 6
// s.order_of_key(25) : Count of elements strictly smaller than 25 is 4




/* Listen music of IU before enjoy my code */

const int LimN = 1e5 + 5;


int NumNode, SpecNode, NumShop, q, timeDFS;
int high[LimN], par[LimN][LOG], LOG2[LimN], w[LimN], f[LimN], num[LimN];
int mnf[LimN][LOG], mng[LimN][LOG], mn[LimN], pref[LimN], suf[LimN];
bool shop[LimN];
pii edge[LimN];

vector<pii> adj[LimN], nadj[LimN];

void make_tree() {
    function<void(int, int)> dfs = [&](int u, int p) {
        num[u] = ++timeDFS;
        for (auto [v, c] : adj[u]) if (v != p) {
            nadj[u].pushb(pii(v, c));
            dfs(v, u);
        }
    };
    dfs(1, 0);
    for (int i = 1; i <= NumNode; i++) {
        swap(adj[i], nadj[i]);
        // cout << i << endl;
        // for (auto [v, c] : adj[i]) cout << v << " " << c << endl;
        // cout << endl;
    }
}

void dfs(int u) {

    for (auto [v, c] : adj[u]) {
        high[v] = high[u] + 1;
        w[v] = w[u] + c;
        par[v][0] = u;
        dfs(v);
    }

    pref[0] = suf[SZ(adj[u]) + 1] = mn[u];
    for (int i = 1; i <= SZ(adj[u]); i++) {
        auto [v, c] = adj[u][i - 1];
        pref[i] = suf[i] = mn[v] + c;
        minimize(pref[i], pref[i - 1]);
    }

    for (int i = SZ(adj[u]); i >= 1; i--) {
        minimize(suf[i], suf[i + 1]);
        auto [v, c] = adj[u][i - 1];
        f[v] = min(pref[i - 1], suf[i + 1]);
        mnf[v][0] = f[v] - w[u];
        mng[v][0] = f[v] + w[u];
    }
    mn[u] = suf[1];

}

bool IsChild(int u, int p) {
    return num[u] >= num[p];
}

int getmnf(int u, int k) {
    int ans = INF;
    // cout << "uk" << u << " " << k << endl;
    for (int i = LOG2[k]; i >= 0; i--) if (k >= MASK(i)) {
        minimize(ans, mnf[u][i]);
        k -= MASK(i);
        u = par[u][i];
    }
    return ans;
}

int getmng(int u, int k) {
    int ans = INF;
    for (int i = LOG2[k]; i >= 0; i--) if (k >= MASK(i)) {
        minimize(ans, mng[u][i]);
        k -= MASK(i);
        u = par[u][i];
    }
    return ans;
}

int jump(int u, int k) {
    for (int i = LOG2[k]; i >= 0; i--) if (k >= MASK(i)) {
        k -= MASK(i);
        u = par[u][i];
    }
    return u;
}

bool ok(int sta, int p, int child) {    
    int oksta = IsChild(sta, child);
    int okspecnode = IsChild(SpecNode, child);
    return !(oksta ^ okspecnode);
}


void RMQ() {
    make_tree();
    high[1] = 1;
    dfs(1);
    for (int i = 2; i <= NumNode; i++) LOG2[i] = LOG2[i / 2] + 1;
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= NumNode; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
            mnf[i][j] = min(mnf[i][j - 1], mnf[par[i][j - 1]][j - 1]);
            mng[i][j] = min(mng[i][j - 1], mng[par[i][j - 1]][j - 1]);
        }
    }
}

int lca(int u, int v) {
    if (high[u] < high[v]) swap(u, v);
    for (int i = LOG2[high[u] - high[v]]; i >= 0; i--) {
        if (high[par[u][i]] >= high[v]) {
            u = par[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LOG2[high[u]]; i >= 0; i--) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}


void solve() {

    cin >> NumNode >> NumShop >> q >> SpecNode;

    for (int i = 1; i < NumNode; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        edge[i] = pii(u, v);
        adj[u].pushb(pii(v, c));
        adj[v].pushb(pii(u, c));
    }

    fill(mn + 1, mn + 1 + NumNode, INF);
    // for (int i = 1; i <= NumNode; i++) cout << mn[i] << " ";
    // cout << endl;
    for (int i = 1; i <= NumShop; i++) {
        int x;
        cin >> x;
        shop[x] = true;
        mn[x] = 0;
        // cout << "shop" << x << endl;
    }

    RMQ();
    for (int i = 1; i < NumNode; i++) {
        auto [u, v] = edge[i];
        if (high[u] > high[v]) swap(edge[i].fi, edge[i].se);
    }
    // for (int i = 1; i <= NumNode; i++) {
    //     cout << i << " " << mn[i] << " " << f[i] << " " << w[i] << endl;
    // }


    for (int i = 1; i <= q; i++) {
        int id, sta;
        cin >> id >> sta;
        auto [p, child] = edge[id];

        if (ok(sta, p, child)) {
            cout << "escaped" << endl;
        }
        else {
            int ans = INF, resa, resb;
            // cout << p << " " << child << endl;
            if (IsChild(p, sta)) {
                // cout << "type1" << endl;
                // cout << f[child] << endl;
                resa = getmng(child, high[child] - high[sta]) - w[sta];
                resb = getmnf(sta, high[sta] - high[1]) + w[sta];
                ans = min(resa, resb);
            }
            else if (IsChild(sta, child)) {
                // cout << "type2" << endl;
                resa = getmnf(sta, high[sta] - high[child]) + w[sta];
                resb = mn[sta];
                // cout << f[sta] << " " << sta << " " << child << " " << resa << endl;
                ans = min(resa, resb);
                // debug;
            }
            else {
                // cout << "type3" << endl;
                int root = lca(sta, p);
                resa = getmnf(sta, high[sta] - high[root]) + w[sta];
                resb = getmng(child, high[child] - high[root]) - w[root] + w[sta];
                ans = min({resa, resb, mn[sta]});
            }
            minimize(ans, INF);
            if (ans == INF) cout << "oo" << endl;
            else cout << ans << endl;
        }

    }
    


}


/* Authors: Nguyen Minh Huy from Le Quy Don high school for Gifted Students Da Nang */



signed main() {

    #ifndef ONLINE_JUDGE
    freopen("ab.inp", "r", stdin);
    freopen("ab.out", "w", stdout);
    #else
    // freopen("task.inp", "r", stdin);
    // freopen("task.out", "w", stdout);
    #endif
    FAST;
    bool TestCase = 0;
    int NumTest = 1;
    //cin >> NumTest;
    for (int i = 1; i <= NumTest; i++) {
        if (TestCase) cout << "Case" << " " << i << ": ";
        solve();
    }

}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:301:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  301 |     freopen("ab.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:302:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  302 |     freopen("ab.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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