結果

問題 No.1524 Upward Mobility
ユーザー aspi
提出日時 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言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
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

ソースコード

diff #
プレゼンテーションモードにする

#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]=ij
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0