結果

問題 No.1030 だんしんぐぱーりない
ユーザー 00 Sakuda00 Sakuda
提出日時 2024-04-04 20:08:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 512 ms / 2,000 ms
コード長 9,075 bytes
コンパイル時間 3,110 ms
コンパイル使用メモリ 236,400 KB
実行使用メモリ 43,956 KB
最終ジャッジ日時 2024-04-04 20:08:25
合計ジャッジ時間 21,496 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
39,348 KB
testcase_01 AC 36 ms
39,348 KB
testcase_02 AC 36 ms
39,348 KB
testcase_03 AC 36 ms
39,348 KB
testcase_04 AC 42 ms
39,348 KB
testcase_05 AC 352 ms
42,932 KB
testcase_06 AC 290 ms
42,676 KB
testcase_07 AC 219 ms
40,884 KB
testcase_08 AC 219 ms
41,652 KB
testcase_09 AC 306 ms
43,444 KB
testcase_10 AC 171 ms
40,116 KB
testcase_11 AC 336 ms
42,036 KB
testcase_12 AC 326 ms
42,036 KB
testcase_13 AC 270 ms
42,292 KB
testcase_14 AC 397 ms
42,804 KB
testcase_15 AC 215 ms
40,756 KB
testcase_16 AC 340 ms
41,524 KB
testcase_17 AC 293 ms
43,060 KB
testcase_18 AC 428 ms
42,932 KB
testcase_19 AC 260 ms
40,372 KB
testcase_20 AC 283 ms
41,140 KB
testcase_21 AC 250 ms
42,164 KB
testcase_22 AC 277 ms
41,140 KB
testcase_23 AC 340 ms
41,396 KB
testcase_24 AC 278 ms
41,012 KB
testcase_25 AC 303 ms
41,908 KB
testcase_26 AC 231 ms
39,860 KB
testcase_27 AC 260 ms
40,116 KB
testcase_28 AC 351 ms
42,036 KB
testcase_29 AC 241 ms
42,164 KB
testcase_30 AC 258 ms
41,140 KB
testcase_31 AC 284 ms
41,140 KB
testcase_32 AC 314 ms
42,676 KB
testcase_33 AC 316 ms
42,676 KB
testcase_34 AC 173 ms
40,500 KB
testcase_35 AC 507 ms
43,956 KB
testcase_36 AC 494 ms
43,956 KB
testcase_37 AC 472 ms
43,956 KB
testcase_38 AC 512 ms
43,956 KB
testcase_39 AC 467 ms
43,956 KB
testcase_40 AC 37 ms
39,348 KB
testcase_41 AC 36 ms
39,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <iomanip>
using namespace std;
using ll = long long;
using VVI = vector<vector<int>>;
using VVL = vector<vector<ll>>;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
using VC = vector<char>;
using VP = vector<pair<int, int>>;
using Graph0 = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define drep(i, a, b) for (int i = (int)(a);i >= (int)(b);i--)
#define urep(i, a, b) for (int i = (int)(a);i <= (int)(b);i++)
#define lrep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ldrep(i, a, b) for (ll i = (ll)(a);i >= (ll)(b);i--)
#define lurep(i, a, b) for (ll i = (ll)(a);i <= (ll)(b);i++)
#define arep(i, v) for (auto i : v)
#define all(a) (a).begin(), (a).end()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define eyes cout << "Yes" << endl;exit(0);
#define eno cout << "No" << endl;exit(0);
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b; 
    return true;
  }
  return false;
}
template<typename T>
void excout(T A) {
  cout << A << endl;
  exit(0);
}
constexpr long long INF = (1LL << 60); // INFにちゅういい！

// 辺の情報
struct Edge
{
  // 行先
  int to;

  // コスト
  int cost;
};

using Graph = std::vector<std::vector<Edge>>;

// { distance, from }
using Pair = std::pair<long long, int>;

// ダイクストラ法 (1.1 基本実装)
// distances は頂点数と同じサイズ, 全要素 INF で初期化しておく
void Dijkstra(const Graph& graph, std::vector<long long>& distances, int startIndex)
{
  // 「現時点での最短距離, 頂点」の順に取り出す priority_queue
  // デフォルトの priority_queue は降順に取り出すため std::greater を使う
  std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> q;
  q.emplace((distances[startIndex] = 0), startIndex);

  while (!q.empty())
  {
    const long long distance = q.top().first;
    const int from = q.top().second;
    q.pop();

    // 最短距離でなければ処理しない
    if (distances[from] < distance)
    {
      continue;
    }

    // 現在の頂点からの各辺について
    for (const auto& edge : graph[from])
    {
      // to までの新しい距離
      const long long d = (distances[from] + edge.cost);

      // d が現在の記録より小さければ更新
      if (d < distances[edge.to])
      {
        q.emplace((distances[edge.to] = d), edge.to);
      }
    }
  }
}
template<typename T>
T MODS(T a, T mods) {
  return ((((((a + mods) % mods) + mods) % mods)));
}
//combination 列挙用 --int ver
VVI comb(int n, int r) {
  VVI v(n + 1, VI (n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}
vector<pair<long long, long long> > prime_factorize(long long N) {
    // 答えを表す可変長配列
    vector<pair<long long, long long> > res;

    // √N まで試し割っていく
    for (long long p = 2; p * p <= N; ++p) {
        // N が p で割り切れないならばスキップ
        if (N % p != 0) {
            continue;
        }

        // N の素因数 p に対する指数を求める
        int e = 0;
        while (N % p == 0) {
            // 指数を 1 増やす
            ++e;

            // N を p で割る
            N /= p;
        }

        // 答えに追加
        res.emplace_back(p, e);
    }

    // 素数が最後に残ることがありうる
    if (N != 1) {
        res.emplace_back(N, 1);
    }
    return res;
}
using UNION_TYPE = int;
struct UnionFind {
    vector<UNION_TYPE> par, siz;
    UnionFind(UNION_TYPE n) : par(n, -1), siz(n, 1) {}
    UNION_TYPE root(UNION_TYPE x) {
        if (par[x] == -1) return x;
        else return par[x] = root(par[x]);
    }
    bool issame(UNION_TYPE x, UNION_TYPE y) {
        return root(x) == root(y);
    }
    bool unite(UNION_TYPE x, UNION_TYPE y) {
        x = root(x);y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        par[y] = x;
        siz[x] += siz[y];
        return true;
    }
    UNION_TYPE size(UNION_TYPE x) {
        return siz[root(x)];
    }
};
//mod func の型に注意！！！
//Union Find はUNION_TYPE で型変可能！
//
VI topo_sort(Graph0& G) {
  int N = G.size();
  VI IND(N, 0);
  rep(v, N) {
    arep(nv, G[v]) {
      IND[nv]++;
    }
  }
  queue<int> que;
  rep(v, N) {
    if (IND[v] == 0) {
      que.push(v);
    }
  }
  VI ANS;
  while (!que.empty()) {
    int v = que.front();
    ANS.push_back(v);
    que.pop();
    arep(nv, G[v]) {
      IND[nv]--;
      if (IND[nv] == 0) {
        que.push(nv);
      }
    }
  }
  return ANS;
}
void ADD(int a, int b, Graph0& G) {
  G[a].push_back(b);
  G[b].push_back(a);
}
VP near(int i, int j, int H, int W) {
  VP ans;
  VP cand = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}};
  arep(v, cand) {
    if (v.first < 0 or v.first >= H) continue;
    if (v.second < 0 or v.second >= W) continue;
    ans.push_back(v);
  }
  return ans;
}
int cast(int i, int j, int H, int W) {
  return ((W * i) + j);
}
ll pows(ll x, ll n, ll mod) {
    if (!n) return 1;
    x %= mod;
    ll r = pows(x, n / 2, mod);
    (r *= r) %= mod;
    if (n % 2) (r *=x) %= mod;
    return r;
}
struct COMB_MOD {
  ll mod;
  int MAX;
  VL fac, finv, inv;
  COMB_MOD(int max, ll m) {
    fac.assign(max, 0);
    finv.assign(max, 0);
    inv.assign(max, 0);
    mod = m;
    MAX = max;
  }
  void solve() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;

        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
    
  }
  ll comb(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
  }
};

struct LCA {
    vector<vector<int>> parent;  // parent[k][u]:= u の 2^k 先の親
    vector<int> dist;            // root からの距離
    LCA(const Graph0 &G, int root = 0) { init(G, root); }

    // 初期化
    void init(const Graph0 &G, int root = 0) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        parent.assign(K, vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; 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]];
                }
            }
        }
    }

    // 根からの距離と1つ先の頂点を求める
    void dfs(const Graph0 &G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e != p) dfs(G, e, v, d + 1);
        }
    }

    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v);  // u の方が深いとする
        int K = parent.size();
        // LCA までの距離を同じにする
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        // 二分探索で LCA を求める
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
    int get_dist(int u, int v) { return dist[u] + dist[v] - 2 * dist[query(u, v)]; }
};
#include <atcoder/segtree>
using namespace atcoder;
int MN = 2e5;
Graph0 G(MN);
LCA lca(G);
VI C(MN);
int op(int a, int b) {
    if (a == -1 or b == -1) return max(a, b);
    return lca.query(a, b);
}
int e() {return -1;} 

VI MX(MN, 0);
void dfs(int v, int par, int mx) {
    MX[v] = max(C[v], mx);
    arep(nv, G[v]) {
        if (nv == par) continue;
        dfs(nv, v, MX[v]);
    }
}
int main(void) {
    int N, K, Q;cin >> N >> K >> Q;
    rep(i, N) cin >> C[i];
    VI A(K + 1, 0);
    urep(i, 1, K) {
        cin >> A[i];
        A[i]--;
    }

    rep(i, N  - 1) {
        int a, b;cin >> a >> b;
        a--;b--;
        ADD(a, b, G);

    }

    LCA lc(G);
    lca = lc;
    segtree<int, op, e> seg(A);
    dfs(0, 0, 0);
    while (Q--) {
        int  t;cin >> t;
        if (t == 1) {
            int x, y;cin >> x >> y;
            y--;
            seg.set(x, y);
        } else {
            int l, r;cin >> l >> r;
            int rt = seg.prod(l, r + 1);
            cout << MX[rt] << endl;
        }
    }
}
0