/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 7ms 8.375 MiB
#2 Accepted 7ms 9.691 MiB
#3 Accepted 7ms 8.309 MiB
#4 Accepted 7ms 9.691 MiB
#5 Accepted 7ms 9.211 MiB
#6 Accepted 7ms 8.395 MiB
#7 Accepted 15ms 9.418 MiB
#8 Accepted 16ms 8.426 MiB
#9 Accepted 16ms 9.371 MiB
#10 Accepted 17ms 9.906 MiB
#11 Accepted 435ms 25.543 MiB
#12 Accepted 431ms 25.152 MiB
#13 Accepted 384ms 25.281 MiB
#14 Accepted 397ms 24.629 MiB
#15 Accepted 173ms 12.461 MiB
#16 Accepted 176ms 13.723 MiB
#17 Accepted 176ms 13.273 MiB
#18 Accepted 184ms 12.609 MiB
#19 Accepted 175ms 12.98 MiB
#20 Accepted 179ms 13.391 MiB

Code

/**
 *    author:  skmonir
 *    created: 01-Feb-2018 19:31:07
**/

#include <bits/stdc++.h>

using namespace std;

#define endl                '\n'
#define TN                  typename
#define all(x)              x.begin(), x.end()
#define rall(x)             x.rbegin(), x.rend()
#define mem(x, y)           memset(x, y, sizeof x)
#define FOR(x, l, r)        for (int x = l; x <= r; ++x)
#define ROF(x, l, r)        for (int x = l; x >= r; --x)

template <TN T> inline void Int(T &n) {
    n = 0; int f = 1; register int ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';
    n = n * f;
}

template <TN T> T gcd(T a, T b) {return !b ? a : gcd(b, a % b);}
template <TN T> inline void umin(T &a, T b) {a = a < b ? a : b;}
template <TN T> inline void umax(T &a, T b) {a = a > b ? a : b;}
template <TN T, TN W> inline void Int(T &x, W &y) {Int(x), Int(y);}
template <TN T, TN W, TN Q> inline void Int(T &x, W &y, Q &z) {Int(x, y), Int(z);}

const int N = 1e5 + 7;
const int inf = 1e9 + 7;
const int mod = 1e9 + 7;


vector <int> idx[N];
vector < pair <int, int> > g[N];
int n, chain, a[N], head[N], belong[N], pos[N];
int dep[N], Par[N][25], sub[N], edgeEnd[N], t[N << 2];

void dfs(int u, int p) {
    sub[u] = 1;
    Par[u][0] = p;
    dep[u] = dep[p] + 1;
    for (int i = 1; i <= 20; i++) {
        Par[u][i] = Par[Par[u][i - 1]][i - 1];
    }
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].first;
        if (v != p) {
            dfs(v, u);
            edgeEnd[idx[u][i]] = v;
            sub[u] += sub[v];
        }
    }
}

int LCA(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int dis = dep[a] - dep[b];
    for (int i = 20; i >= 0; i--) {
        if (dis & (1 << i)) a = Par[a][i];
    }
    for (int i = 20; i >= 0; i--) {
        if (Par[a][i] != Par[b][i]) {
            a = Par[a][i], b = Par[b][i];
        }
    }
    return a == b ? a : Par[a][0];
}

void upd(int nd, int s, int e, int l, int r, int w) {
    if (e < l or r < s) return;
    if (s >= l and e <= r) {
        t[nd] = w; return;
    }
    int md = (s + e) >> 1;
    upd(nd << 1, s, md, l, r, w);
    upd(nd << 1 | 1, md + 1, e, l, r, w);
    t[nd] = max(t[nd << 1], t[nd << 1 | 1]);
}

int ask(int nd, int s, int e, int l, int r) {
    if (e < l or r < s) return 0;
    int md = (s + e) >> 1;
    if (s >= l and e <= r) return t[nd];
    int c1 = ask(nd << 1, s, md, l, r);
    int c2 = ask(nd << 1 | 1, md + 1, e, l, r);
    return max(c1, c2);
}

void HLD(int u, int p, int w) {
    if (head[chain] == -1) head[chain] = u;
    belong[u] = chain;
    pos[u] = ++n;
    a[n] = w;

    int nextv = -1, nextw = 0;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].first;
        int w = g[u][i].second;
        if (v == p) continue;
        if (nextv == -1 or sub[nextv] < sub[v]) {
            nextv = v, nextw = w;
        }
    }

    if (~nextv) HLD(nextv, u, nextw);

    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].first;
        int w = g[u][i].second;
        if (v == p or v == nextv) continue;
        chain++;
        HLD(v, u, w);
    }
}

int query_up(int u, int v) {
    if (u == v) return 0;
    int uchain, vchain, res = 0;
    while (1) {
        uchain = belong[u], vchain = belong[v];
        if (uchain == vchain) {
            if (u == v) break;
            umax(res, ask(1, 1, n, pos[v] + 1, pos[u]));
            break;
        }
        umax(res, ask(1, 1, n, pos[head[uchain]], pos[u]));
        u = Par[head[uchain]][0];
    }
    return res;
}

int query(int u, int v) {
    int l = LCA(u, v);
    return max(query_up(u, l), query_up(v, l));
}

int main() {
    //freopen("input_A.txt", "r", stdin);
    int tc = 1;
    while (tc--) {
        mem(head, -1);
        n = 0, chain = 1;
        for (int i = 0; i < N; i++) {
            g[i].clear();
            idx[i].clear();
        }

        int n, m; scanf("%d %d", &n, &m);
        for (int i = 1; i < n; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            g[u].push_back({v, w});
            g[v].push_back({u, w});
            idx[u].push_back(i - 1);
            idx[v].push_back(i - 1);
        }
        dfs(1, 0);
        HLD(1, 0, 0);
        for (int i = 1; i <= n; i++) {
            upd(1, 1, n, i, i, a[i]);
        }
        while (m--) {
            int u, v;
            scanf("%d%d", &u, &v);
            printf("%d\n", query(u, v));
        }
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1019 Graph Stuff
Language
C++17 (G++ 13.2.0)
Submit At
2024-01-03 16:17:28
Judged At
2024-11-11 03:44:36
Judged By
Score
100
Total Time
435ms
Peak Memory
25.543 MiB