結果

問題 No.1833 Subway Planning
ユーザー fuppy_kyoprofuppy_kyopro
提出日時 2022-02-04 22:37:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 902 ms / 4,000 ms
コード長 11,195 bytes
コンパイル時間 3,505 ms
コンパイル使用メモリ 232,836 KB
実行使用メモリ 69,276 KB
最終ジャッジ日時 2024-06-11 12:09:35
合計ジャッジ時間 15,739 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,964 KB
testcase_01 AC 5 ms
7,968 KB
testcase_02 AC 4 ms
7,896 KB
testcase_03 AC 3 ms
7,760 KB
testcase_04 AC 340 ms
68,888 KB
testcase_05 AC 499 ms
69,276 KB
testcase_06 AC 406 ms
67,524 KB
testcase_07 AC 733 ms
67,208 KB
testcase_08 AC 763 ms
62,824 KB
testcase_09 AC 899 ms
68,876 KB
testcase_10 AC 380 ms
53,532 KB
testcase_11 AC 441 ms
53,456 KB
testcase_12 AC 468 ms
55,484 KB
testcase_13 AC 390 ms
53,368 KB
testcase_14 AC 343 ms
52,000 KB
testcase_15 AC 724 ms
53,656 KB
testcase_16 AC 509 ms
51,084 KB
testcase_17 AC 902 ms
52,544 KB
testcase_18 AC 818 ms
50,932 KB
testcase_19 AC 663 ms
51,292 KB
testcase_20 AC 461 ms
45,232 KB
testcase_21 AC 616 ms
62,056 KB
testcase_22 AC 499 ms
58,272 KB
testcase_23 AC 4 ms
7,896 KB
testcase_24 AC 4 ms
8,004 KB
testcase_25 AC 4 ms
7,932 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//*/

#include <bits/stdc++.h>

// #include <atcoder/all>
// #include <atcoder/modint>

using namespace std;
// using namespace atcoder;

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define DEBUG_VEC(v)                                        \
    cerr << #v << ":";                                      \
    for (int iiiiiiii = 0; iiiiiiii < v.size(); iiiiiiii++) \
        cerr << " " << v[iiiiiiii];                         \
    cerr << endl;
#define DEBUG_MAT(v)                                \
    cerr << #v << endl;                             \
    for (int iv = 0; iv < v.size(); iv++) {         \
        for (int jv = 0; jv < v[iv].size(); jv++) { \
            cerr << v[iv][jv] << " ";               \
        }                                           \
        cerr << endl;                               \
    }
typedef long long ll;
// #define int ll

#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define vs vector<string>
#define pii pair<int, int>
#define pis pair<int, string>
#define psi pair<string, int>
#define pll pair<ll, ll>
template <class S, class T>
pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) {
    return pair<S, T>(s.first + t.first, s.second + t.second);
}
template <class S, class T>
pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template <class S, class T>
ostream &operator<<(ostream &os, pair<S, T> p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}
#define X first
#define Y second
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rrep1(i, n) for (int i = (int)(n); i > 0; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(), c.end()
void YES(bool t = true) {
    cout << (t ? "YES" : "NO") << endl;
}
void Yes(bool t = true) { cout << (t ? "Yes" : "No") << endl; }
void yes(bool t = true) { cout << (t ? "yes" : "no") << endl; }
void NO(bool t = true) { cout << (t ? "NO" : "YES") << endl; }
void No(bool t = true) { cout << (t ? "No" : "Yes") << endl; }
void no(bool t = true) { cout << (t ? "no" : "yes") << endl; }
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
int popcount(ll t) { return __builtin_popcountll(t); }
// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0};
// vi dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };
struct Setup_io {
    Setup_io() {
        ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cout << fixed << setprecision(25);
    }
} setup_io;
// const ll MOD = 1000000007;
const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'

class HLD {
  private:
    void dfs_sz(int v) {
        for (int &u : G[v])
            if (u == par[v]) swap(u, G[v].back());
        if (~par[v]) G[v].pop_back();

        for (int &u : G[v]) {
            par[u] = v;
            dep[u] = dep[v] + 1;
            dfs_sz(u);
            sub[v] += sub[u];
            if (sub[u] > sub[G[v][0]]) swap(u, G[v][0]);
        }
    }

    void dfs_hld(int v, int c, int &pos) {
        vid[v] = pos++;
        inv[vid[v]] = v;
        type[v] = c;
        for (int u : G[v]) {
            if (u == par[v]) continue;
            head[u] = (u == G[v][0] ? head[v] : u);
            dfs_hld(u, c, pos);
        }
    }

  public:
    vector<vector<int>> G;
    vector<int> vid, head, sub, par, dep, inv, type;

    HLD(int n) : G(n), vid(n, -1), head(n), sub(n, 1),
                 par(n, -1), dep(n, 0), inv(n), type(n) {}

    void add_edge(int u, int v) {
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    void build(vector<int> rs = {0}) {
        int c = 0, pos = 0;
        for (int r : rs) {
            dfs_sz(r);
            head[r] = r;
            dfs_hld(r, c++, pos);
        }
    }

    int lca(int u, int v) {
        while (1) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }

    int distance(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }

    // for_each(vertex)
    // [l, r) <- attention!!
    template <typename F>
    void for_each(int u, int v, const F &f) {
        while (1) {
            if (vid[u] > vid[v]) swap(u, v);
            f(max(vid[head[v]], vid[u]), vid[v] + 1);
            if (head[u] != head[v])
                v = par[head[v]];
            else
                break;
        }
    }

    template <typename T, typename Q, typename F>
    T for_each(int u, int v, T ti, const Q &q, const F &f) {
        T l = ti, r = ti;
        while (1) {
            if (vid[u] > vid[v]) {
                swap(u, v);
                swap(l, r);
            }
            l = f(l, q(max(vid[head[v]], vid[u]), vid[v] + 1));
            if (head[u] != head[v])
                v = par[head[v]];
            else
                break;
        }
        return f(l, r);
    }

    // for_each(edge)
    // [l, r) <- attention!!
    template <typename F>
    void for_each_edge(int u, int v, const F &f) {
        while (1) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] != head[v]) {
                f(vid[head[v]], vid[v] + 1);
                v = par[head[v]];
            } else {
                if (u != v) {
                    f(vid[u] + 1, vid[v] + 1);
                }
                break;
            }
        }
    }
};

template <typename T1, typename T2>
class LazySegmentTree {
  public:
    using F = function<T1(T1 &, T1 &)>;           // query_func
    using G = function<T2(T2 &, T2 &)>;           // update_func
    using H = function<T1(T1 &, T2 &, int, int)>; // lazy to node (node, lazy, left, right)
    int n;
    vector<T1> node;
    vector<T2> lazy;
    T1 e1;
    T2 e2;
    F query_func;
    G update_func;
    H eval_func;

    LazySegmentTree(vector<T1> a, F query_func, G update_func, H eval_func, T1 e1, T2 e2)
        : query_func(query_func), update_func(update_func), eval_func(eval_func), e1(e1), e2(e2) {
        int _n = a.size();
        n = 1;
        while (n < _n)
            n *= 2;
        node.resize(2 * n - 1, e1);
        lazy.resize(2 * n - 1, e2);
        for (int i = 0; i < _n; i++)
            node[i + n - 1] = a[i];
        for (int i = n - 2; i >= 0; i--) {
            node[i] = query_func(node[i * 2 + 1], node[i * 2 + 2]);
        }
    }

    // k�Ԗڂ̃m�[�h�ɂ‚��Ēx���]�����s��
    inline void eval(int k, int l, int r) {
        if (lazy[k] != e2) { // Change
            node[k] = eval_func(node[k], lazy[k], l, r);
            if (r - l > 1) {
                lazy[2 * k + 1] = update_func(lazy[2 * k + 1], lazy[k]);
                lazy[2 * k + 2] = update_func(lazy[2 * k + 2], lazy[k]);
            }
            lazy[k] = e2; // Change
        }
    }

    // [a, b)��x�ɂ���
    void update(int a, int b, T2 x, int k, int l, int r) {
        // k �Ԗڂ̃m�[�h�ɑ΂��Ēx���]�����s��
        eval(k, l, r);
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            lazy[k] = update_func(lazy[k], x);
            eval(k, l, r);
        } else {
            update(a, b, x, 2 * k + 1, l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = query_func(node[2 * k + 1], node[2 * k + 2]);
        }
    }

    void update(int a, int b, T2 x) {
        update(a, b, x, 0, 0, n);
    }

    T1 query(int a, int b, int k, int l, int r) {
        eval(k, l, r);
        if (b <= l || r <= a) return e1;
        if (a <= l && r <= b) return node[k];
        T1 resl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        T1 resr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return query_func(resl, resr);
    }

    T1 query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};

const int N = 200011;
vii G(N);

void dfs(int now, int par, vi &val) {
    for (int ch : G[now]) {
        if (ch == par) continue;
        dfs(ch, now, val);
        val[now] += val[ch];
    }
}

signed main() {
    int n;
    cin >> n;

    HLD hld(n);
    vi u(n - 1), v(n - 1), c(n - 1);
    rep(i, n - 1) {
        cin >> u[i] >> v[i] >> c[i];
        u[i]--;
        v[i]--;
        G[u[i]].push_back(v[i]);
        G[v[i]].push_back(u[i]);
        hld.add_edge(u[i], v[i]);
    }

    hld.build();

    auto f1 = [](ll a, ll b) { return max(a, b); };
    auto g = [](ll a, ll b) { return b; };
    auto h = [](ll a, ll b, int l, int r) { return b; };
    LazySegmentTree<ll, ll> seg_ma(vl(n), f1, g, h, -INF, INF);

    auto f2 = [](ll a, ll b) { return min(a, b); };
    LazySegmentTree<ll, ll> seg_mi(vl(n), f2, g, h, INF, -INF);

    rep(i, n - 1) {
        auto f1 = [&](ll a, ll b) { seg_ma.update(a, b, c[i]); };
        hld.for_each_edge(u[i], v[i], f1);
        auto f2 = [&](ll a, ll b) { seg_mi.update(a, b, c[i]); };
        hld.for_each_edge(u[i], v[i], f2);
    }

    int ok = inf + 10, ng = -1;

    vi val(n);
    while (ng + 1 < ok) {
        int mid = (ng + ok) / 2;
        // if (mid < 3) {
        //     DEBUG(mid);
        // }

        vi us;
        rep(i, n - 1) {
            if (c[i] <= mid) continue;
            us.push_back(u[i]);
            us.push_back(v[i]);
        }

        if (us.size() == 0) {
            ok = mid;
            continue;
        }

        fill(all(val), 0);
        int lc = us[0];
        for (int u : us) {
            val[u] = 1;
            lc = hld.lca(u, lc);
        }

        dfs(0, -1, val);

        vi leaf;
        rep(i, n) {
            if (val[i] == 1) {
                leaf.push_back(i);
            }
        }
        assert(leaf.size() > 0);

        if (leaf.size() > 2) {
            ng = mid;
            continue;
        }

        int lc2 = leaf[0];
        for (int u : leaf) {
            lc2 = hld.lca(u, lc2);
        }

        if (leaf.size() == 2 && lc != lc2) {
            ng = mid;
            continue;
        }

        ll mi = INF, ma = -INF;
        auto f1 = [&](int a, int b) { mi = min(mi, seg_mi.query(a, b)); };
        auto f2 = [&](int a, int b) { ma = max(ma, seg_ma.query(a, b)); };

        for (int u : leaf) {
            hld.for_each_edge(u, lc, f1);
            hld.for_each_edge(u, lc, f2);
        }

        if (ma - mi <= mid)
            ok = mid;
        else
            ng = mid;
    }

    cout << ok << endl;
}
0