結果

問題 No.1524 Upward Mobility
ユーザー aspiaspi
提出日時 2021-05-28 19:22:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,523 ms / 6,000 ms
コード長 7,139 bytes
コンパイル時間 1,442 ms
コンパイル使用メモリ 104,432 KB
実行使用メモリ 251,116 KB
最終ジャッジ日時 2024-11-07 07:24:29
合計ジャッジ時間 47,148 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,039 ms
38,496 KB
testcase_01 AC 1,149 ms
38,592 KB
testcase_02 AC 3,523 ms
52,608 KB
testcase_03 AC 817 ms
95,692 KB
testcase_04 AC 2,787 ms
52,224 KB
testcase_05 AC 2,768 ms
54,656 KB
testcase_06 AC 2,688 ms
57,472 KB
testcase_07 AC 2,815 ms
56,232 KB
testcase_08 AC 2,661 ms
54,656 KB
testcase_09 AC 2,651 ms
55,852 KB
testcase_10 AC 2,624 ms
60,772 KB
testcase_11 AC 338 ms
60,284 KB
testcase_12 AC 278 ms
60,160 KB
testcase_13 AC 764 ms
60,276 KB
testcase_14 AC 780 ms
160,344 KB
testcase_15 AC 937 ms
148,736 KB
testcase_16 AC 2,559 ms
56,320 KB
testcase_17 AC 2,059 ms
49,600 KB
testcase_18 AC 320 ms
14,336 KB
testcase_19 AC 1,777 ms
46,720 KB
testcase_20 AC 459 ms
19,712 KB
testcase_21 AC 553 ms
22,144 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 604 ms
251,116 KB
testcase_30 AC 600 ms
250,988 KB
testcase_31 AC 825 ms
250,988 KB
testcase_32 AC 2,974 ms
57,472 KB
権限があれば一括ダウンロードができます

ソースコード

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 size, limit, depth, queryl = 0, queryr = 0;
	S scopy; F fcopy;
	bool (*g)(S);

	inline S getsum(node* np) { return np ? np->sum : e(); }
	inline 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));
		}
	}
	int max_right(node* np, int l, int r) {
		if (r <= queryl || !np)return -1;
		eval(np, r - l > 1);
		if (g(op(scopy, np->sum))) {
			scopy = op(scopy, np->sum);
			return -1;
		}
		if (r - l == 1) return l;
		int v;
		if ((v = max_right(np->child[0], l, (l + r) / 2)) != -1)return v;
		if ((v = max_right(np->child[1], (l + r) / 2, r)) != -1)return v;
		return -1;
	}
	int min_left(node* np, int l, int r) {
		if (queryr <= l || !np)return -1;
		eval(np, r - l > 1);
		if (g(op(scopy, np->sum))) {
			scopy = op(scopy, np->sum);
			return -1;
		}
		if (r - l == 1)return r;
		int v;
		if ((v = min_left(np->child[1], (l + r) / 2, r)) != -1)return v;
		if ((v = min_left(np->child[0], l, (l + r) / 2)) != -1)return v;
		return -1;
	}
	public:
		dynamic_lazysegtree(int N) {
			assert(0 < N);
			size = 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);
		}
		template <class Fn> int max_right(int l, Fn temp) {
			assert(0 <= l && l < limit);
			queryl = l;
			scopy = e();
			g = temp;
			int ret = max_right(root, 0, limit);
			if (ret != -1) return ret;
			return size;
		}
		template <class Fn> int min_left(int r, Fn temp) {
			assert(0 < r && r <= limit);
			queryr = r;
			scopy = e();
			g = temp;
			int ret = min_left(root, 0, limit);
			if (ret != -1) return ret;
			return 0;
		}
		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, threshold;
vector<vector<int>>tree; //木グラフ
vector<pair<int, int>>numbers; //木の頂点に乗っている数
vector<set<int>>elements; //頂点iより下の部分木にある要素
vector<mysegtree*> dp; //dpテーブル
//dp[i][j]=i番目のノードで下限がjのとき、そのノードより下の部分木で最高得点

bool func(long long x) {
	return x < threshold;
}

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;
	}
	/*
	long long pos = numbers[x].first - 1,
		update = (*dp[x]).prod(pos, N) + numbers[x].second;
	threshold = update;
	int l = dp[x]->min_left(pos + 1, func);
	*/

	(*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;
}
0