#466114 (C++14) No.1030 だんしんぐぱーりない

提出ソース

結果

問題	No.1030 だんしんぐぱーりない
ユーザー	tsutaj
提出日時	2020-04-17 22:58:40
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	321 ms / 2,000 ms
コード長	6,305 bytes
コンパイル時間	1,455 ms
コンパイル使用メモリ	120,752 KB
実行使用メモリ	27,376 KB
最終ジャッジ日時	2024-04-14 15:19:24
合計ジャッジ時間	10,437 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	214 ms 23,888 KB
testcase_06	AC	174 ms 18,960 KB
testcase_07	AC	113 ms 9,984 KB
testcase_08	AC	119 ms 12,416 KB
testcase_09	AC	174 ms 24,176 KB
testcase_10	AC	77 ms 6,940 KB
testcase_11	AC	197 ms 14,336 KB
testcase_12	AC	180 ms 21,512 KB
testcase_13	AC	163 ms 19,728 KB
testcase_14	AC	229 ms 19,420 KB
testcase_15	AC	100 ms 6,940 KB
testcase_16	AC	199 ms 16,796 KB
testcase_17	AC	185 ms 24,724 KB
testcase_18	AC	248 ms 20,108 KB
testcase_19	AC	131 ms 8,960 KB
testcase_20	AC	149 ms 14,420 KB
testcase_21	AC	139 ms 18,280 KB
testcase_22	AC	147 ms 14,920 KB
testcase_23	AC	200 ms 13,568 KB
testcase_24	AC	142 ms 8,192 KB
testcase_25	AC	173 ms 13,440 KB
testcase_26	AC	104 ms 6,944 KB
testcase_27	AC	119 ms 6,940 KB
testcase_28	AC	199 ms 17,408 KB
testcase_29	AC	133 ms 21,240 KB
testcase_30	AC	140 ms 15,360 KB
testcase_31	AC	149 ms 13,792 KB
testcase_32	AC	185 ms 19,132 KB
testcase_33	AC	182 ms 22,272 KB
testcase_34	AC	81 ms 7,296 KB
testcase_35	AC	321 ms 27,368 KB
testcase_36	AC	288 ms 27,376 KB
testcase_37	AC	310 ms 27,364 KB
testcase_38	AC	310 ms 27,368 KB
testcase_39	AC	291 ms 27,368 KB
testcase_40	AC	2 ms 6,940 KB
testcase_41	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

// @category セグメント木 (Segment Tree)
// @title セグメント木 (Segment Tree)
// 抽象 SegmentTree (0-indexed・一点更新・区間取得)
template <typename MonoidType>
struct SegmentTree {
    using Function = function< MonoidType(MonoidType, MonoidType) >;

    // node, identity element
    int n, orig_n;
    vector<MonoidType> node;
    MonoidType E0;

    // update / combine function
    Function upd_f, cmb_f;

    void build(int m, vector<MonoidType> v = vector<MonoidType>()) {
        if(v != vector<MonoidType>()) m = v.size();
        n = 1; while(n < m) n *= 2;

        node = vector<MonoidType>(2*n-1, E0);
        if(v != vector<MonoidType>()) {
            for(int i=0; i<m; i++) {
                node[n-1+i] = v[i];
            }
            for(int i=n-2; i>=0; i--) {
                node[i] = cmb_f(node[2*i+1], node[2*i+2]);
            }
        }
    }

    // initialize
    SegmentTree() {}
    SegmentTree(int n_, MonoidType E0_,
                Function upd_f_, Function cmb_f_,
                vector<MonoidType> v = vector<MonoidType>()) :
        E0(E0_), upd_f(upd_f_), cmb_f(cmb_f_) {
        build(n_, v);
        orig_n = n_;
    }

    // update k-th element (applied value: x)
    void update(int k, MonoidType x) {
        k += n - 1;
        node[k] = upd_f(node[k], x);
        while(k > 0) {
            k = (k - 1) / 2;
            node[k] = cmb_f(node[2*k+1], node[2*k+2]);
        }
    }

    // range query for [a, b)
    // 非再帰のアイデア: http://d.hatena.ne.jp/komiyam/20131202/1385992406
    MonoidType query(int a, int b) {
        assert(a >= 0 and a < b and b <= orig_n);
        MonoidType vl = node[n-1+a], vr = node[n-1+b-1];
        for(int l=a+n, r=b+n; l<r; l>>=1, r>>=1) {
            if(l & 1) vl = cmb_f(vl, node[(l++)-1]);
            if(r & 1) vr = cmb_f(node[(--r)-1], vr);
        }
        return cmb_f(vl, vr);
    }
};

// 移動元と行先と辺のコストを記録する構造体
template <typename T = int>
struct Edge {
    int from, to;
    T cost;
    Edge(int s, T d = 1) : to(s), cost(d) {}
    Edge(int f, int s, T d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};

template <typename T = int>
using Graph = vector< vector< Edge<T> > >;


// 最小共通先祖 (Lowest Common Ancestor, LCA) を求める
// Verified: AOJ GRL_5_C (Lowest Common Ancestor)

template <typename T>
struct TreeLCA {
public:
    int const MAX_LOG_V;
    vector< vector< Edge<T> > > G;
    int root, vn;
    vector< vector<int> > parent;
    vector<int> depth;

    // constructor (Graph, root)
    TreeLCA(vector< vector< Edge<T> > > &_G, int _r) : 
        MAX_LOG_V(20), G(_G), root(_r), vn(G.size()), 
        parent(MAX_LOG_V, vector<int>(vn, 0)), depth(vn, -1)
        { depth[root] = 0; init(vn); }

    void dfs(int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for(int i=0; i<G[v].size(); i++) {
            if(depth[ G[v][i].to ] >= 0) continue;
            if(G[v][i].to != p) dfs(G[v][i].to, v, d+1);
        }
    }

    void init(int V) {
        dfs(root, -1, 0);
        for(int k=0; k+1 < MAX_LOG_V; k++) {
            for(int v=0; v < V; v++) {
                if(parent[k][v] < 0) parent[k+1][v] = -1;
                else parent[k+1][v] = parent[k][parent[k][v]];
            }
        }
    }

    // u と v の最小共通祖先
    int lca(int u, int v) {
        if(depth[u] > depth[v]) swap(u, v);
        for(int k=0; k < MAX_LOG_V; k++) {
            if((depth[v] - depth[u]) >> k & 1) {
                v = parent[k][v];
            }
        }
        if(u == v) return u;
        for(int k=MAX_LOG_V - 1; k>=0; k--) {
            if(parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

    // u と v のパスの長さ (LCA を使って計算)
    int dist(int u, int v) {
        int anc = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[anc];
    }
};

int main() {
    int N, K, Q; scanf("%d%d%d", &N, &K, &Q);
    vector<int> C(N), M(N);
    for(int i=0; i<N; i++) scanf("%d", &C[i]);

    vector<int> A(K);
    for(int i=0; i<K; i++) scanf("%d", &A[i]), A[i]--;

    vector< vector< Edge<> > > G(N);
    for(int i=0; i+1<N; i++) {
        int u, v; scanf("%d%d", &u, &v);
        u--; v--;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    auto dfs = [&](auto &&self, int cur, int par) -> void {
        chmax(M[cur], C[cur]);
        for(auto e : G[cur]) {
            int to = e.to;
            if(to == par) continue;
            chmax(M[to], M[cur]);
            self(self, to, cur);
        }
    };
    dfs(dfs, 0, -1);

    TreeLCA<int> lc(G, 0);
    SegmentTree<int> seg(K, -1,
                         [](int a, int b) { return b; },
                         [&lc](int a, int b) { return lc.lca(a, b); },
                         A);

    while(Q--) {
        int t; scanf("%d", &t);
        if(t == 1) {
            int x, y; scanf("%d%d", &x, &y);
            x--; y--;
            seg.update(x, y);
        }
        if(t == 2) {
            int l, r; scanf("%d%d", &l, &r); l--;
            printf("%d\n", M[seg.query(l, r)]);
        }
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード