結果

問題 No.1524 Upward Mobility
ユーザー aspiaspi
提出日時 2021-05-03 16:24:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 5,400 bytes
コンパイル時間 3,189 ms
コンパイル使用メモリ 104,740 KB
実行使用メモリ 818,048 KB
最終ジャッジ日時 2024-10-08 20:47:01
合計ジャッジ時間 9,198 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 MLE -
testcase_02 MLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます

ソースコード

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<int, int> f, long long x) {
	if (f.second == -1) return x + f.first;
	return f.second;
}
pair<int, int> composition(pair<int, int> f1, pair<int, int> 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<int, int> id() { return make_pair(0, -1); } //加算 代入


using mysegtree = dynamic_lazysegtree<long long, op, e, pair<int, int>, 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]]);
	}
	int 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