結果

問題 No.1524 Upward Mobility
コンテスト
ユーザー aspi
提出日時 2021-05-04 22:47:37
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,478 bytes
コンパイル時間 2,494 ms
コンパイル使用メモリ 115,952 KB
最終ジャッジ日時 2025-01-21 06:55:32
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'void dfs(int)':
main.cpp:171:25: error: reference to 'numbers' is ambiguous
  171 |         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:143:23: note:                 'std::vector<std::pair<int, int> > numbers'
  143 | vector<pair<int, int>>numbers; //木の頂点に乗っている数
      |                       ^~~~~~~
main.cpp:173:16: error: 'r' was not declared in this scope
  173 |         while (r - l > 1) {
      |                ^
main.cpp:173:20: error: 'l' was not declared in this scope
  173 |         while (r - l > 1) {
      |                    ^
main.cpp:175:42: error: 'update' was not declared in this scope
  175 |                 if (dp[x].get(mi

ソースコード

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* 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;
		}
		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]]);
	}
	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, mysegtree(N));
	for (int i = 0; i < N; i++)dp[i] = mysegtree(N);
	dfs(0);
	cout << dp[0].all_prod() << endl;
}
0