結果
問題 | No.1030 だんしんぐぱーりない |
ユーザー | 👑 null |
提出日時 | 2020-04-17 23:57:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 275 ms / 2,000 ms |
コード長 | 9,309 bytes |
コンパイル時間 | 2,114 ms |
コンパイル使用メモリ | 152,384 KB |
実行使用メモリ | 43,228 KB |
最終ジャッジ日時 | 2024-04-14 16:15:52 |
合計ジャッジ時間 | 9,815 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 201 ms
37,548 KB |
testcase_06 | AC | 153 ms
28,484 KB |
testcase_07 | AC | 87 ms
13,720 KB |
testcase_08 | AC | 98 ms
17,568 KB |
testcase_09 | AC | 182 ms
38,116 KB |
testcase_10 | AC | 53 ms
8,148 KB |
testcase_11 | AC | 143 ms
20,420 KB |
testcase_12 | AC | 188 ms
35,184 KB |
testcase_13 | AC | 151 ms
30,412 KB |
testcase_14 | AC | 187 ms
29,508 KB |
testcase_15 | AC | 56 ms
6,940 KB |
testcase_16 | AC | 164 ms
26,408 KB |
testcase_17 | AC | 191 ms
39,652 KB |
testcase_18 | AC | 199 ms
31,008 KB |
testcase_19 | AC | 95 ms
12,864 KB |
testcase_20 | AC | 137 ms
22,108 KB |
testcase_21 | AC | 139 ms
28,256 KB |
testcase_22 | AC | 132 ms
23,260 KB |
testcase_23 | AC | 145 ms
20,340 KB |
testcase_24 | AC | 91 ms
9,924 KB |
testcase_25 | AC | 130 ms
19,564 KB |
testcase_26 | AC | 65 ms
6,944 KB |
testcase_27 | AC | 72 ms
6,944 KB |
testcase_28 | AC | 174 ms
26,896 KB |
testcase_29 | AC | 159 ms
34,504 KB |
testcase_30 | AC | 130 ms
24,212 KB |
testcase_31 | AC | 129 ms
21,016 KB |
testcase_32 | AC | 163 ms
28,696 KB |
testcase_33 | AC | 200 ms
34,928 KB |
testcase_34 | AC | 57 ms
9,632 KB |
testcase_35 | AC | 275 ms
43,080 KB |
testcase_36 | AC | 267 ms
43,072 KB |
testcase_37 | AC | 268 ms
43,228 KB |
testcase_38 | AC | 274 ms
43,108 KB |
testcase_39 | AC | 268 ms
43,072 KB |
testcase_40 | AC | 2 ms
6,944 KB |
testcase_41 | AC | 2 ms
6,940 KB |
ソースコード
/* このコード、と~おれ! Be accepted! ∧_∧ (。・ω・。)つ━☆・*。 ⊂ ノ ・゜+. しーJ °。+ *´¨) .· ´¸.·*´¨) ¸.·*¨) (¸.·´ (¸.·'* ☆ */ #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <vector> #include <numeric> #include <iostream> #include <random> #include <map> #include <unordered_map> #include <queue> #include <regex> #include <functional> #include <complex> #include <list> #include <cassert> #include <iomanip> #include <set> #include <stack> #include <bitset> /*多倍長整数/cpp_intで宣言 #include <boost/multiprecision/cpp_int.hpp> using namespace boost::multiprecision; */ //#pragma gcc target ("avx2") //#pragma gcc optimization ("o3") //#pragma gcc optimization ("unroll-loops") #define rep(i, n) for(int i = 0; i < (n); ++i) #define rep1(i, n) for(int i = 1; i <= (n); ++i) #define rep2(i, n) for(int i = 2; i < (n); ++i) #define repr(i, n) for(int i = n; i >= 0; --i) #define reprm(i, n) for(int i = n - 1; i >= 0; --i) #define printynl(a) printf(a ? "yes\n" : "no\n") #define printyn(a) printf(a ? "Yes\n" : "No\n") #define printYN(a) printf(a ? "YES\n" : "NO\n") #define printim(a) printf(a ? "possible\n" : "imposible\n") #define printdb(a) printf("%.50lf\n", a) //少数出力 #define printLdb(a) printf("%.50Lf\n", a) //少数出力 #define printdbd(a) printf("%.16lf\n", a) //少数出力(桁少なめ) #define prints(s) printf("%s\n", s.c_str()) //string出力 #define all(x) (x).begin(), (x).end() #define allsum(a, b, c) ((a + b) * c / 2LL) //等差数列の和、初項,末項,項数 #define pb push_back #define priq priority_queue #define rpriq priq<int, vector<int>, greater<int>> #define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI) #define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L) #define Please return #define AC 0 #define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d)) /*(a, b) から (c, d) のマンハッタン距離 */ using ll = long long; constexpr int INF = 1073741823; constexpr int MINF = -1073741823; constexpr ll LINF = ll(4661686018427387903); constexpr ll MOD = 1000000007; const long double PI = acosl(-1.0L); using namespace std; void scans(string& str) { char c; str = ""; scanf("%c", &c); if (c == '\n')scanf("%c", &c); while (c != '\n' && c != -1 && c != ' ') { str += c; scanf("%c", &c); } } void scanc(char& str) { char c; scanf("%c", &c); if (c == -1)return; while (c == '\n') { scanf("%c", &c); } str = c; } double acot(double x) { return PI / 2 - atan(x); } ll LSB(ll n) { return (n & (-n)); } /*-----------------------------------------ここからコード-----------------------------------------*/ //RMQ <O(n log n), O(1)> template<typename T> struct sparsetable { vector<vector<T>> table; vector<int> logtable; vector<int> a; int n; // 渡す配列, サイズ sparsetable(const vector<T> a, int siz) : n(siz), a(a) { logtable.assign(n + 1, 0); for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; table.assign(n, vector<T>(logtable[n] + 1, 0)); } //リストバージョン sparsetable(initializer_list<T> init) { a = init[0]; n = init[1]; logtable.assign(n + 1, 0); for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; table.assign(n, vector<T>(logtable[n] + 1, 0)); } //配列と大きさを渡して初期化 void init(const vector<T> aa, int siz) { a = aa; n = siz; logtable.assign(n + 1, 0); for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; table.assign(n, vector<T>(logtable[n] + 1, 0)); } //構築 O(n log n) void build() { for (int k = 0; (1 << k) <= n; ++k) { for (int i = 0; i + (1 << k) <= n; ++i) { if (k) table[i][k] = (a[table[i][k - 1]] < a[table[i + (1 << (k - 1))][k - 1]] ? table[i][k - 1] : table[i + (1 << (k - 1))][k - 1]); else table[i][k] = i; } } } //[l, r) の RMQ O(1) int query(int l, int r) { int k = logtable[r - l]; return (a[table[l][k]] < a[table[r - (1 << k)][k]] ? table[l][k] : table[r - (1 << k)][k]); } }; //depends on SparseTable //euler tour を行う。O(n) void eulertour(const int& now, const int& bef, int& cnt, const vector<vector<int>>& graph, const int& d, vector<int>& vs, vector<int>& depth, vector<int>& id) { depth.emplace_back(d); vs.emplace_back(now); id[now] = min(id[now], cnt); for (const auto& aa : graph[now]) { if (aa != bef) { ++cnt; eulertour(aa, now, cnt, graph, d + 1, vs, depth, id); ++cnt; depth.emplace_back(d); vs.emplace_back(now); } } } //LCA <O(n log n), O(1)> struct LCA { vector<int> vs, depth, id, tmp = { 0 }; vector<vector<int>> tree; sparsetable<int> table{ tmp, 0 }; int n, root; //木, 大きさ, 根で初期化 LCA(vector<vector<int>> tree, int n, int root) : tree(tree), n(n), root(root) { id.assign(n, INF); } //構築 O(n) + O(n log n) void build() { int cnt = 0, d = 0; eulertour(root, -1, cnt, tree, d, vs, depth, id); table.init(depth, depth.size()); table.build(); } //LCA である頂点を返す O(1) int query(int l, int r) { if (id[l] > id[r])swap(l, r); return vs[table.query(id[l], id[r] + 1)]; } //頂点 n の深さを返す O(1) int depthq(int n) { return depth[id[n]]; } }; //セグ木/0-indexed/非再帰/(大きさ, 単位元)で初期化 template<typename T> struct segtree { //木を配列であらわしたもの vector<T> seg; //木の1/2の大きさ int siz; //単位元 const T e; //比較関数の型 using F = function<T(T, T)>; //マージする関数 const F f; //n の大きさ, a (単位元) で segtree を初期化する segtree(int n, const T a, const F f) : e(a), f(f) { siz = 1; while (siz < n)siz <<= 1; seg.assign(2 * siz - 1, e); --siz; } //k (0-indexed) 番目に t を代入 void set(int k, const T& t) { seg[k + siz] = t; } //f によって木を構築 void build() { for (int i = siz - 1; i >= 0; --i) seg[i] = f(seg[i * 2 + 1], seg[i * 2 + 2]); } //i 番目の要素を返す T operator[](const int i) { return seg[i + siz]; } //k 番目の値を a に更新 void update(int k, T a) { k += siz; //必要であればここを変える seg[k] = a; while (k > 0) { k = ((k - 1) >> 1); seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2]); } } //[a, b) について f した結果を返す T query(int a, int b) { T l = e, r = e; for (a += siz, b += siz; a < b; a >>= 1, b >>= 1) { if (!(a & 1)) { if (l != e)l = f(l, seg[a++]); else l = seg[a++]; } if (!(b & 1)) { if (r != e)r = f(seg[--b], r); else r = seg[--b]; } } if (l == e)l = r; else if (r == e)r = l; return f(l, r); } //[start, end) について、[l, r) を調べながら k 番目が check を満たすか二分探索 最後が true なら left, false なら right fの逆演算 template<typename C> int find(const int start, const int end, int l, int r, int k, const C check, T& checknum, const bool b, const function<T(T, T)> revf) { //cerr << checknum << '\n'; //範囲外またはそこがすでに満たさないとき //cerr << k << ',' << checknum << '\n'; if (start <= l && r <= end && !check(seg[k], checknum)) { checknum = revf(checknum, seg[k]); return -1; } if ((r <= start || l >= end)) { return -1; } //既に葉 if (k >= siz) { return k - siz; } int res; if (b) { //左側を調べる res = find< C >(start, end, l, ((l + r) >> 1), (k << 1) + 1, check, checknum, b, revf); //左側が適してたらそれが答え if (res != -1)return (res); return find< C >(start, end, ((l + r) >> 1), r, (k << 1) + 2, check, checknum, b, revf); } else { //右側を調べる res = find< C >(start, end, ((l + r) >> 1), r, (k << 1) + 2, check, checknum, b, revf); //右側が適してたらそれが答え if (res != -1)return (res); return find< C >(start, end, l, ((l + r) >> 1), (k << 1) + 1, check, checknum, b, revf); } } template<typename C> int find_left(int start, int end, const C check, T checknum, function<T(T, T)> revf) { return find< C >(start, end, 0, siz + 1, 0, check, checknum, true, revf); } template<typename C> int find_right(int start, int end, const C check, T checknum, function<T(T, T)> revf) { return find< C >(start, end, 0, siz + 1, 0, check, checknum, false, revf); } }; void dfs(const vector<vector<int>>& g, const int& now, int& ans, const vector<int> &c) { ans = max(ans, c[now]); for (const auto& aa : g[now])dfs(g, aa, ans, c); } int main() { int n, k, q; scanf("%d%d%d", &n, &k, &q); vector<int> c(n), a(k); rep(i, n)scanf("%d", &c[i]); rep(i, k) { scanf("%d", &a[i]); --a[i]; } vector<vector<int>> tree(n), g(n); int e, f; rep(i, n - 1) { scanf("%d%d", &e, &f); --e; --f; tree[f].push_back(e); g[e].push_back(f); } LCA lca(tree, n, 0); lca.build(); auto fun = [&](int a, int b) {return lca.query(a, b); }; segtree<int> seg(k, -1, fun); rep(i, k)seg.set(i, a[i]); seg.build(); int t, x, y; rep(i, q) { scanf("%d%d%d", &t, &x, &y); if (t == 1) { seg.update(--x, --y); } else { int l = seg.query(--x, y), ans = c[0]; dfs(g, l, ans, c); printf("%d\n", ans); } } Please AC; }