Submission #987667

#	Time	Username	Problem	Language	Result	Execution time	Memory
987667		NoLove	Valley (BOI19_valley)	C++14	23 / 100	298 ms	85444 KiB

valley

/**
 *    author : Lăng Trọng Đạt
 *    created: 23-05-2024 
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int long long
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e18;
const int MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;
int g[MAXN];
int n, s, q, root, r;
vector<pii> adj[MAXN];

pii up[20][MAXN];
int mn[20][MAXN];

bool is_shop[MAXN];
int far[MAXN], lca[2*MAXN];
int get(int x) { return (far[x] == 0 ? x : far[x] = get(far[x])); }
vector<pair<int, int>> query_lcas[MAXN];
int l[MAXN]; // shortest length from node u to shop which is in subtree of u
int d[MAXN]; // length of path from root to node u
int depth[MAXN];
void dfs(int v, int prv, int steps, int dist) {
    d[v] = dist;
    depth[v] = steps;
    if (is_shop[v]) l[v] = 0;
    for (auto[u, w] : adj[v]) {
        if (u == prv) continue;
        dfs(u, v, steps + 1, dist + w);
        mi(l[v], l[u] + w);
        far[u] = v;
        up[0][u].f = v;
        up[0][u].se = l[u];
        if (is_shop[u]) up[0][u].se = d[u];
        mn[0][u] = d[u] - l[u];
    }

    for (auto[u, id] : query_lcas[v]) {
        if (depth[u]) {
            lca[id] = get(u);
        }
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("hi.inp", "r")) {
        freopen("hi.inp", "r", stdin);
//        freopen("hi.out", "w", stdout);
    } 


    // input
    cin >> n >> s >> q >> root;
    int a, b, w;
    vector<pii> edges;
    FOR(i, 1, n - 1) {
        cin >> a >> b >> w;
        adj[a].pb({b, w});
        adj[b].pb({a, w});
        edges.pb({a, b});
    }
    FOR(i, 1, s) {
        cin >> a;
        is_shop[a] = 1;
    }
    vector<pii> Q(q + 1);
    FOR(i, 1, q) {
        cin >> Q[i].f >> Q[i].se;
        int r = Q[i].se;
        auto[a, b] = edges[Q[i].f - 1];
        query_lcas[r].pb({a, i});
        query_lcas[a].pb({r, i});
        query_lcas[r].pb({b, q + i});
        query_lcas[b].pb({r, q + i});
    }

    // preprocess
    memset(l, 0x3f, sizeof(l));
    dfs(root, -1, 1, 0);

    FOR(i, 1, 19) {
        FOR(v, 1, n) {
            up[i][v].f = up[i - 1][up[i - 1][v].f].f;
            if (up[i - 1][v].se) up[i][v].se = up[i - 1][v].se;
            else if (up[i - 1][up[i - 1][v].f].se) 
                up[i][v].se = up[i - 1][up[i - 1][v].f].se;
            mn[i][v] = max(mn[i - 1][v], mn[i - 1][up[i - 1][v].f]);
        }
    }

    // answer query
    FOR(i, 1, q) {
        auto[a, b] = edges[Q[i].f - 1];
        if (depth[a] < depth[b] && lca[i + q] != b) cout << "escaped\n";
        else if (depth[a] > depth[b] && lca[i] != a) cout << "escaped\n";
        else {
            int tren = a, r = Q[i].se;
            if (depth[a] < depth[b]) tren = b;
            if (l[tren] > INF) cout << "oo\n";
            else {
                db(tren, d[tren], d[r])
                int ans = min(l[tren] + d[r] - d[tren], l[r]);
                int jump = depth[r] - depth[tren];
                int shop_in_path = -1;
                int tmp = r;
                FOR(i, 0, 19) {
                    if ((1 << i) && jump) {
                        if (up[i][tmp].se != 0) {
                            if (shop_in_path != -1) {
                                mi(ans, d[r] - d[shop_in_path]);
                                shop_in_path = up[i][tmp].se;
                            }
                        }
                        mi(ans, d[r] - mn[i][tmp]);
                        tmp = up[i][tmp].f;
                    }
                }

                cout << ans << "\n";   
            }
        }
    }
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
valley.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     for (auto[u, w] : adj[v]) {
      |              ^
valley.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for (auto[u, id] : query_lcas[v]) {
      |              ^
valley.cpp: In function 'int32_t main()':
valley.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
valley.cpp:74:5: note: in expansion of macro 'FOR'
   74 |     FOR(i, 1, n - 1) {
      |     ^~~
valley.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
valley.cpp:80:5: note: in expansion of macro 'FOR'
   80 |     FOR(i, 1, s) {
      |     ^~~
valley.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
valley.cpp:85:5: note: in expansion of macro 'FOR'
   85 |     FOR(i, 1, q) {
      |     ^~~
valley.cpp:88:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |         auto[a, b] = edges[Q[i].f - 1];
      |             ^
valley.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
valley.cpp:99:5: note: in expansion of macro 'FOR'
   99 |     FOR(i, 1, 19) {
      |     ^~~
valley.cpp:18:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
valley.cpp:100:9: note: in expansion of macro 'FOR'
  100 |         FOR(v, 1, n) {
      |         ^~~
valley.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
valley.cpp:110:5: note: in expansion of macro 'FOR'
  110 |     FOR(i, 1, q) {
      |     ^~~
valley.cpp:111:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |         auto[a, b] = edges[Q[i].f - 1];
      |             ^
valley.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
valley.cpp:124:17: note: in expansion of macro 'FOR'
  124 |                 FOR(i, 0, 19) {
      |                 ^~~
valley.cpp:125:28: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
  125 |                     if ((1 << i) && jump) {
      |                         ~~~^~~~~
valley.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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