結果
問題 | No.1524 Upward Mobility |
ユーザー |
![]() |
提出日時 | 2021-05-12 00:52:31 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,698 bytes |
コンパイル時間 | 2,266 ms |
コンパイル使用メモリ | 115,128 KB |
最終ジャッジ日時 | 2025-01-21 10:11:30 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function 'void dfs(int)': main.cpp:182:25: error: reference to 'numbers' is ambiguous 182 | long long pos = numbers[x].first - 1, l = 0, r = pos + 1, | ^~~~~~~ In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/max_size_type.h:37, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/ranges_base.h:38, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/string_view:50, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/basic_string.h:47, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/string:53, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/locale_classes.h:40, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/ios_base.h:41, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/ios:42, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/ostream:38, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/iostream:39, from main.cpp:1: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/numbers:48:11: note: candidates are: 'namespace std::numbers { }' 48 | namespace numbers | ^~~~~~~ main.cpp:153:23: note: 'std::vector<std::pair<int, int> > numbers' 153 | vector<pair<int, int>>numbers; //木の頂点に乗っている数 | ^~~~~~~ main.cpp:184:16: error: 'r' was not declared in this scope 184 | while (r - l > 1) { | ^ main.cpp:184:20: error: 'l' was not declared in this scope 184 | while (r - l > 1) { | ^ main.cpp:186:45: error: 'update' was not declared in this scope 186 | if ((*dp[x]).get
ソースコード
#include <iostream>#include <vector>#include <utility>#include <algorithm>#include <set>#include <cassert>using namespace std;template<class T>bool chmax(T& xx, T yy) { if (xx < yy) { xx = yy; return true; }return false; }template <class S,S(*op)(S, S),S(*e)(),class F,S(*mapping)(F, S),F(*composition)(F, F),F(*id)()>class dynamic_lazysegtree {struct node {S sum;F lazy;node* child[2];node() {sum = e();lazy = id();child[0] = nullptr;child[1] = nullptr;}~node() {if (child[0])delete child[0];if (child[1])delete child[1];}};node* root = new node();int limit, depth, queryl = 0, queryr = 0;S scopy; F fcopy;S getsum(node* np) { return np ? np->sum : e(); }void eval(node*& np, bool bo) {if (np->lazy == id())return;if (bo) { //子に伝播if (!np->child[0]) np->child[0] = new node();np->child[0]->lazy = composition(np->lazy, np->child[0]->lazy);if (!np->child[1])np->child[1] = new node();np->child[1]->lazy = composition(np->lazy, np->child[1]->lazy);}np->sum = mapping(np->lazy, np->sum);np->lazy = id();}void set(node*& np, int pos, int dep) {if (!np) np = new node();eval(np, dep >= 0);if (dep == -1) {np->sum = scopy;return;}set(np->child[(bool)(pos & (1 << dep))], pos, dep - 1);np->sum = op(getsum(np->child[0]), getsum(np->child[1]));return;}void apply(node*& np, int l, int r) {if (!np)np = new node();eval(np, r - l > 1);if (queryl <= l && r <= queryr) {np->lazy = composition(fcopy, np->lazy);eval(np, r - l > 1);}else if (queryl < r && l < queryr) {apply(np->child[0], l, (l + r) / 2);apply(np->child[1], (l + r) / 2, r);np->sum = op(getsum(np->child[0]), getsum(np->child[1]));}}S prod(node* np, int l, int r) {if (r <= queryl || queryr <= l || !np) {return e();}eval(np, r - l > 1);if (queryl <= l && r <= queryr) {return np->sum;}else {return op(prod(np->child[0], l, (l + r) / 2), prod(np->child[1], (l + r) / 2, r));}}public:dynamic_lazysegtree(int N) {assert(0 < N);depth = 0;while ((1U << depth) < (unsigned int)(N)) depth++;limit = 1 << depth;}dynamic_lazysegtree() {depth = 0;limit = 1;}~dynamic_lazysegtree() {delete root;}void set(int pos, S x) {assert(0 <= pos && pos < limit);scopy = x;set(root, pos, depth - 1);}S get(int pos) {assert(0 <= pos && pos < limit);node* np = root;for (int i = depth - 1; i >= 0; i--) {eval(np, true);np = np->child[(bool)(pos & (1 << i))];if (!np)return e();}eval(np, false);return np->sum;}void apply(int l, int r, F x) {assert(0 <= l && l <= r && r <= limit);if (l == r)return;queryl = l; queryr = r; fcopy = x;apply(root, 0, limit);}S prod(int l, int r) {assert(0 <= l && l <= r && r <= limit);if (l == r)return e();queryl = l; queryr = r;return prod(root, 0, limit);}S all_prod() {eval(root, true);return root->sum;}};long long op(long long x, long long y) { return max(x, y); }long long e() { return 0; }long long mapping(pair<long long, long long> f, long long x) {if (f.second == -1) return x + f.first;return f.second;}pair<long long, long long> composition(pair<long long, long long> f1, pair<long long, long long> f2) {if (f1.second != -1) return make_pair(0, f1.second);if (f2.second == -1) return make_pair(f2.first + f1.first, -1);return make_pair(0, f2.second + f1.first);}pair<long long, long long> id() { return make_pair(0, -1); } //加算 代入using mysegtree = dynamic_lazysegtree<long long, op, e, pair<long long, long long>, mapping, composition, id>;int N;vector<vector<int>>tree; //木グラフvector<pair<int, int>>numbers; //木の頂点に乗っている数vector<set<int>>elements; //頂点iより下の部分木にある要素vector<mysegtree*> dp; //dpテーブル//dp[i][j]=i番目のノードで下限がjのとき、そのノードより下の部分木で最高得点void dfs(int x) {for (int i = 0; i < tree[x].size(); i++) {dfs(tree[x][i]);}int a = -1/*子部分木の中で頂点数が最大の物のindex*/, b = -1/* elememts[a].size()*/;for (int i = 0; i < tree[x].size(); i++) {if (chmax(b, (int)elements[tree[x][i]].size())) a = i;}if (a != -1) {swap(dp[x], dp[tree[x][a]]);swap(elements[x], elements[tree[x][a]]);}for (int i = 0; i < tree[x].size(); i++) {if (i == a)continue;long long m = 0;for (auto itr = elements[tree[x][i]].rbegin(); itr != elements[tree[x][i]].rend(); ) {chmax(m, (*dp[tree[x][i]]).get(*itr));int r = *itr + 1, l = (++itr == elements[tree[x][i]].rend() ? 0 : *itr + 1);(*dp[x]).apply(l, r, make_pair(m, -1));}elements[x].merge(elements[tree[x][i]]);delete dp[tree[x][i]];}long long pos = numbers[x].first - 1, l = 0, r = pos + 1,update = (*dp[x]).prod(pos, N) + numbers[x].second;while (r - l > 1) {int mid = (l + r) / 2;if ((*dp[x]).get(mid - 1) < update) r = mid;else l = mid;}(*dp[x]).apply(l, pos + 1, make_pair(0, update));elements[x].insert(pos);}signed main() {cin.tie(nullptr);ios::sync_with_stdio(false);cin >> N;tree.resize(N);numbers.resize(N);elements.resize(N);int a;for (int i = 1; i < N; i++) { //木の構築cin >> a;tree[a - 1].push_back(i);}for (int i = 0; i < N; i++) { //入力cin >> a;numbers[i].first = a;}for (int i = 0; i < N; i++) { //入力cin >> a;numbers[i].second = a;}dp.resize(N);for (int i = 0; i < N; i++)dp[i] = new mysegtree(N);dfs(0);cout << (*dp[0]).all_prod() << endl;}