結果

問題 No.1030 だんしんぐぱーりない
ユーザー Jumbo_kprJumbo_kpr
提出日時 2020-04-18 05:07:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,530 ms / 2,000 ms
コード長 11,603 bytes
コンパイル時間 2,561 ms
コンパイル使用メモリ 159,652 KB
実行使用メモリ 27,264 KB
最終ジャッジ日時 2024-04-27 03:10:56
合計ジャッジ時間 36,322 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1,013 ms
24,448 KB
testcase_06 AC 732 ms
19,344 KB
testcase_07 AC 601 ms
9,216 KB
testcase_08 AC 542 ms
11,264 KB
testcase_09 AC 614 ms
23,936 KB
testcase_10 AC 418 ms
6,940 KB
testcase_11 AC 1,003 ms
12,928 KB
testcase_12 AC 1,053 ms
24,056 KB
testcase_13 AC 680 ms
20,096 KB
testcase_14 AC 1,171 ms
19,804 KB
testcase_15 AC 417 ms
6,944 KB
testcase_16 AC 1,157 ms
17,152 KB
testcase_17 AC 751 ms
26,756 KB
testcase_18 AC 1,258 ms
20,920 KB
testcase_19 AC 789 ms
10,492 KB
testcase_20 AC 962 ms
14,720 KB
testcase_21 AC 651 ms
18,048 KB
testcase_22 AC 843 ms
16,936 KB
testcase_23 AC 1,088 ms
14,792 KB
testcase_24 AC 755 ms
6,940 KB
testcase_25 AC 848 ms
12,416 KB
testcase_26 AC 594 ms
6,940 KB
testcase_27 AC 641 ms
6,940 KB
testcase_28 AC 1,137 ms
18,520 KB
testcase_29 AC 632 ms
23,756 KB
testcase_30 AC 795 ms
17,376 KB
testcase_31 AC 873 ms
13,824 KB
testcase_32 AC 841 ms
18,176 KB
testcase_33 AC 917 ms
23,912 KB
testcase_34 AC 413 ms
8,380 KB
testcase_35 AC 1,462 ms
27,216 KB
testcase_36 AC 1,521 ms
27,192 KB
testcase_37 AC 1,530 ms
27,136 KB
testcase_38 AC 1,524 ms
27,136 KB
testcase_39 AC 1,506 ms
27,264 KB
testcase_40 AC 2 ms
6,944 KB
testcase_41 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
//#pragma warning(disable : 4996)

#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif

#include <limits.h>
#include <math.h>
#include <time.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m - 1; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v, n) reverse(v, v + n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout << (x) << '\n'
#define pe(x) cout << (x) << " "
#define DEBUG(x) cout << #x << ": " << x << endl
#define lb(v, n) lower_bound(v.begin(), v.end(), (n))
#define ub(v, n) upper_bound(v.begin(), v.end(), (n))
//#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i, v.size()) cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template <typename T1, typename T2> inline void chmin(T1& a, T2 b) {
    if (a > b) a = b;
}
template <typename T1, typename T2> inline void chmax(T1& a, T2 b) {
    if (a < b) a = b;
}
typedef pair<int, int> pii;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7;
constexpr int MAX = 2000020;
const double pi = acos(-1);
constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;
void yes(bool c) {
    if (c)
        print("Yes");
    else
        print("No");
};

// const int mod = 1000000007;
const int mod = 998244353;
struct mint {
    ll x;  // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

template <typename T> struct edge {
    int src, to;
    T cost;
    edge(int to) : src(-1), to(to), cost(1) {}
    edge(int to, T cost) : src(-1), to(to), cost(cost) {}
    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
    edge& operator=(const int& x) {
        to = x;
        return *this;
    }
    operator int() const { return to; }
};
template <typename T> using Edges = vector<edge<T>>;
template <typename T> using Graph = vector<Edges<T>>;

template <typename T> struct HeavyLightDecomposition {
    Graph<T> G;

    // next: child which makes heavy edge
    // head: head of heavy edge
    vector<int> sz, par, next, head, depth, index;
    int N;
    HeavyLightDecomposition(Graph<T>& g) : G(g) {
        N = G.size();
        sz.assign(N, 0);
        par.assign(N, 0);
        next.assign(N, -1);
        head.assign(N, 0);
        depth.assign(N, 0);
        index.assign(N, 0);
        build();
    }
    int dfs(int n) {
        int siz = 1, mx = 0;
        for (auto e : G[n]) {
            int nxt = e.to;
            if (nxt == par[n]) continue;
            par[nxt] = n;
            siz += dfs(nxt);
            if (sz[nxt] > mx) {
                mx = sz[nxt];
                next[n] = nxt;  // heavy edge
            }
        }
        return sz[n] = siz;
    }
    void assign_number() {
        queue<pair<int, int>> que;  // push the head of heavy edge
        que.push({0, 0});
        int idx = 0;
        while (!que.empty()) {
            int n = que.front().first;
            int d = que.front().second;
            que.pop();
            index[n] = idx++;
            depth[n] = d;
            int h = n;
            head[n] = n;
            while (next[n] != -1) {
                for (auto e : G[n]) {
                    int nxt = e.to;
                    if (nxt == par[n] || nxt == next[n]) continue;
                    que.push({nxt, d + 1});
                }
                n = next[n];
                index[n] = idx++;
                depth[n] = d;
                head[n] = h;
            }
        }
    }
    void build() {
        dfs(0);
        assign_number();
    }
    int lca(int u, int v) {
        if (u == v) return u;
        if (depth[u] > depth[v]) swap(u, v);
        while (depth[u] < depth[v]) {
            v = par[head[v]];
        }
        // if u and v begong to the same array
        if (head[u] == head[v]) {
            if (index[u] < index[v])
                return u;
            else
                return v;
        } else {
            u = par[head[u]];
            v = par[head[v]];
            return lca(u, v);
        }
    }
    vector<pair<int, int>> query(int u, int v) {
        vector<pair<int, int>> ret;
        if (depth[u] > depth[v]) swap(u, v);
        while (depth[u] < depth[v]) {
            int l = index[head[v]], r = index[v] + 1;
            ret.push_back({l, r});
            v = par[head[v]];
        }
        // if u and v begong to the same array
        if (head[u] == head[v]) {
            if (index[u] > index[v]) swap(u, v);
            int l = index[u], r = index[v] + 1;
            ret.push_back({l, r});
        }
        return ret;
    }
};
template <typename T> struct SegmentTree {
    int n;
    T unit;
    vector<T> dat;
    function<T(T, T)> func;
    SegmentTree(const int N, T _unit, function<T(T, T)> _func) : unit(_unit), func(_func) {
        n = 1;
        //簡単のため、要素数を2のべき乗に
        while (n < N) n *= 2;
        dat.assign(2 * n, unit);
    }

    void update(int k, T a) {
        k += n - 1;  //葉の節点
        dat[k] = a;
        //上りながら更新
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    T _query(int a, int b, int k, int l, int r) {
        //[a,b)と[l,r)が交差していなければ、funcに影響を与えない値を返す
        if (r <= a || b <= l) return unit;
        //[a,b)が[l,r)を完全に含んでいれば、この節点の値
        if (a <= l && r <= b)
            return dat[k];
        else {
            int vl = _query(a, b, k * 2 + 1, l, (l + r) / 2);
            int vr = _query(a, b, k * 2 + 2, (l + r) / 2, r);
            return func(vl, vr);
        }
    }
    //[a,b)
    T query(int a, int b) { return _query(a, b, 0, 0, n); }
};
// auto f = [](int a, int b) {return a + b; };
// SegmentTree<int>seg(N,0,f);

template <typename Semigroup> struct DisjointSparseTable {
    using F = function<Semigroup(Semigroup, Semigroup)>;
    const F f;
    vector<vector<Semigroup>> st;

    DisjointSparseTable(const vector<Semigroup>& v, const F& f) : f(f) {
        int b = 0;
        while ((1 << b) <= v.size()) ++b;
        st.resize(b, vector<Semigroup>(v.size(), Semigroup()));
        for (int i = 0; i < v.size(); i++) st[0][i] = v[i];
        for (int i = 1; i < b; i++) {
            int shift = 1 << i;
            for (int j = 0; j < v.size(); j += shift << 1) {
                int t = min(j + shift, (int)v.size());
                st[i][t - 1] = v[t - 1];
                for (int k = t - 2; k >= j; k--) st[i][k] = f(v[k], st[i][k + 1]);
                if (v.size() <= t) break;
                st[i][t] = v[t];
                int r = min(t + shift, (int)v.size());
                for (int k = t + 1; k < r; k++) st[i][k] = f(st[i][k - 1], v[k]);
            }
        }
    }

    Semigroup query(int l, int r) {
        if (l >= --r) return st[0][l];
        int p = 31 - __builtin_clz(l ^ r);
        return f(st[p][l], st[p][r]);
    }
};

const int SIZE = 334;
int C[200010], A[200010];
int who[200010];
int par[201010];
//[l,r)
int calc_par(int l, int r, HeavyLightDecomposition<int>& hl) {
    int p = A[l];
    int idx = l;
    while (idx < r) {
        if (idx % SIZE == 0 && idx + SIZE <= r) {
            p = hl.lca(p, par[idx / SIZE]);
            idx += SIZE;
        } else {
            p = hl.lca(p, A[idx]);
            idx++;
        }
    }
    return p;
}
int N, K;
int update(int idx, HeavyLightDecomposition<int>& hl) {
    int i = idx / SIZE;
    par[i] = A[i * SIZE];
    FOR(j, i * SIZE, i * SIZE + SIZE) {
        if (j >= K) break;
        par[i] = hl.lca(par[i], A[j]);
    }
    return par[i];
}
void solve() {
    cin >> N;
    int Q;
    cin >> K >> Q;
    Graph<int> G(N);
    REP(i, N) cin >> C[i];
    REP(i, K) {
        cin >> A[i];
        A[i]--;
        who[A[i]] = i;
    }
    REP(i, N - 1) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        if (u > v) swap(u, v);
        edge<int> e(v);
        G[u].push_back(e);
        edge<int> e2(u);
        G[v].push_back(e2);
    }
    HeavyLightDecomposition<int> hl(G);
    auto f = [](int a, int b) { return max(a, b); };
    vector<int> v(N);
    REP(i, N) { v[hl.index[i]] = C[i]; }
    DisjointSparseTable<int> table(v, f);
    // auto f = [](int a, int b) { return max(a, b); };
    // SegmentTree<int> seg(N, 0, f);
    // REP(i, N)seg.update(i, C[i]);

    // REP(i, N) seg.update(hl.index[i], C[i]);
    int cnt = (K + SIZE - 1) / SIZE;
    REP(i, cnt) {
        par[i] = A[i * SIZE];
        REP(j, SIZE) {
            int v = i * SIZE + j;
            if (v >= K) break;
            int p = hl.lca(par[i], A[v]);
            par[i] = p;
        }
    }
    // REP(i, cnt) {
    //	cout << i * SIZE << " " << i * SIZE + SIZE << ":" << par[i]+1 << endl;
    //}
    REP(_, Q) {
        int T;
        cin >> T;
        if (T == 2) {
            int l, r;
            cin >> l >> r;
            l--, r;
            int p = calc_par(l, r, hl);
            vector<pii> ps = hl.query(0, p);
            int res = 0;
            // cerr << "par:" << p + 1 << endl;
            for (auto pp : ps) {
                // cerr << pp.first+1 << " " << pp.second+1 << endl;
                res = max(res, table.query(pp.first, pp.second));
            }
            // cerr << "par:" << p + 1 << endl;
            // int res = seg.query(0, p + 1);
            print(res);
        } else {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            A[x] = y;
            update(x, hl);
            // seg.update(hl.index[x], C[A[x]]);
        }
    }
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // int q; cin >> q;
    // while (q--)
    solve();
}
0