Submission #1094317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094317		anha3k25cvp	Valley (BOI19_valley)	C++17	23 / 100	85 ms	26316 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const ll inf = 7 + 1e18;

struct Edge {
    int u, v, w;
};

int node = 0, logn;
vector <int> in, ou, h;
vector <ll> f;
vector <Edge> e;
vector <vector <int>> adj, p;

void dfs(int u) {
    in[u] = ++ node;
    for (int i : adj[u]) {
        int v = e[i].u + e[i].v - u;
        if (!in[v]) {
            h[v] = h[u] + 1;
            p[0][v] = u;
            f[v] = f[u] + e[i].w;
            dfs(v);
        }
    }
    ou[u] = node;
}

int lca(int u, int v) {
    if (h[u] < h[v])
        swap(u, v);
    for (int si = h[u] - h[v]; si > 0; si ^= si & -si) {
        int i = __builtin_ctz(si & -si);
        u = p[i][u];
    }
    if (u == v)
        return u;
    for (int i = logn - 1; i >= 0; i --)
        if (p[i][u] != p[i][v]) {
            u = p[i][u];
            v = p[i][v];
        }
    return p[0][u];
}

ll dis(int u, int v) {
    return f[u] + f[v] - f[lca(u, v)] * 2;
}

vector <int> siz, pre;

void dfs(int u, int par) {
    siz[u] = 1;
    for (int i : adj[u]) {
        int v = e[i].u + e[i].v - u;
        if (v != par && pre[v] < 0) {
            dfs(v, u);
            siz[u] += siz[v];
        }
    }
}

int centroid(int u, int par) {
    for (int i : adj[u]) {
        int v = e[i].u + e[i].v - u;
        if (pre[v] < 0 && v != par && siz[v] * 2 > siz[u])
            return centroid(v, u);
    }
    return u;
}

void build(int u, int par) {
    dfs(u, par);
    int c = centroid(u, par);
    pre[c] = par;
    for (int i : adj[c]) {
        int v = e[i].u + e[i].v - c;
        if (pre[v] < 0)
            build(v, c);
    }
}

vector <int> lg;

bool cmp(int u, int v) {
    return in[u] < in[v];
}

struct Tree {
    vector <ll> a;
    vector <vector <ll>> mi;
    void build(int root) {
        int n = a.size();
        sort(a.begin(), a.end(), cmp);
        mi.assign(logn, vector <ll> (n, 0));
        for (int i = 0; i < n; i ++)
            mi[0][i] = dis(a[i], root);
        for (int i = 1; i < logn; i ++)
            for (int u = 0; u < n; u ++)
                if (u + (1 << i) - 1 < n)
                    mi[i][u] = min(mi[i - 1][u], mi[i - 1][u + (1 << (i - 1))]);
    }
    ll get_min(int l, int r) {
        if (l > r)
            return inf;
        int bit = lg[r - l + 1];
        return min(mi[bit][l], mi[bit][r - (1 << bit) + 1]);
    }
    ll get_ans(int l, int r, int type) {
        if (a.empty())
            return inf;
        int n = a.size(), lo = 0, hi = n - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (in[a[mid]] >= l)
                hi = mid;
            else
                lo = mid + 1;
        }
        if (type) {
            if (l <= in[a[lo]] && in[a[lo]] <= r) {
                int L = lo;
                hi = n - 1;
                while (lo < hi) {
                    int mid = (lo + hi + 1) / 2;
                    if (in[a[mid]] <= r)
                        lo = mid;
                    else
                        hi = mid - 1;
                }
                return get_min(L, lo);
            }
            return inf;
        }
        if (l <= in[a[lo]] && in[a[lo]] <= r) {
            int L = lo;
            hi = n - 1;
            while (lo < hi) {
                int mid = (lo + hi + 1) / 2;
                if (in[a[mid]] <= r)
                    lo = mid;
                else
                    hi = mid - 1;
            }
            return min(get_min(1, L - 1), get_min(lo + 1, n - 1));
        }
        return get_min(0, n - 1);
    }
};

vector <Tree> T;

void update(int u) {
    int v = u;
    while (v > 0) {
        T[v].a.push_back(u);
        v = pre[v];
    }
}

int main() {
#define TASKNAME ""
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen( TASKNAME".inp", "r", stdin );
        freopen( TASKNAME".out", "w", stdout );
    }
    int n, s, q, root;
    cin >> n >> s >> q >> root;
    e.resize(n);
    adj.resize(n + 1);
    for (int i = 1; i < n; i ++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        adj[e[i].u].push_back(i);
        adj[e[i].v].push_back(i);
    }
    vector <int> a(n + 1, 0);
    for (int i = 1; i <= s; i ++) {
        int u;
        cin >> u;
        a[u] = 1;
    }
    for (logn = 1; (1 << logn) <= n; logn ++);
    p.assign(logn, vector <int> (n + 1, 0));
    in.assign(n + 1, 0);
    ou.assign(n + 1, 0);
    h.assign(n + 1, 0);
    f.assign(n + 1, 0);
    h[1] = 1;
    dfs(1);
    for (int i = 1; i < logn; i ++)
        for (int u = 1; u <= n; u ++)
            p[i][u] = p[i - 1][p[i - 1][u]];
    for (int i = 1; i < n; i ++)
        if (in[e[i].u] > in[e[i].v])
            swap(e[i].u, e[i].v);
    if (s == n) {
        while (q --) {
            int id, u;
            cin >> id >> u;
            int l = in[e[id].v], r = ou[e[id].v], check = (l <= in[u] && in[u] <= r), v = u,
                check1 = (l <= in[root] && in[root] <= r);
            if (check == check1) {
                cout << "escaped\n";
                continue;
            }
            cout << "0\n";
        }
        return 0;
    }
    siz.assign(n + 1, 0);
    pre.assign(n + 1, -1);
    build(1, 0);
    lg.assign(n + 1, 0);
    for (int i = 2; i <= n; i ++)
        lg[i] = lg[i >> 1] + 1;
    T.resize(n + 1);
    for (int i = 1; i <= n; i ++)
        if (a[i])
            update(i);
    for (int i = 1; i <= n; i ++)
        T[i].build(i);
    while (q --) {
        int id, u;
        cin >> id >> u;
        int l = in[e[id].v], r = ou[e[id].v], check = (l <= in[u] && in[u] <= r), v = u,
            check1 = (l <= in[root] && in[root] <= r);
        if (check == check1) {
            cout << "escaped\n";
            continue;
        }
        if (a[u]) {
            cout << "0\n";
            continue;
        }
        ll mi = inf;
        while (v > 0) {
            ll val = T[v].get_ans(l, r, check);
            if (val < inf)
                mi = min(mi, dis(u, v) + val);
            v = pre[v];
        }
        if (mi < inf)
            cout << mi << '\n';
        else
            cout << "oo\n";
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:210:87: warning: unused variable 'v' [-Wunused-variable]
  210 |             int l = in[e[id].v], r = ou[e[id].v], check = (l <= in[u] && in[u] <= r), v = u,
      |                                                                                       ^
valley.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         freopen( TASKNAME".inp", "r", stdin );
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen( TASKNAME".out", "w", stdout );
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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