結果
問題 | No.1524 Upward Mobility |
ユーザー |
![]() |
提出日時 | 2021-05-28 20:53:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 427 ms / 6,000 ms |
コード長 | 3,390 bytes |
コンパイル時間 | 2,425 ms |
コンパイル使用メモリ | 189,536 KB |
実行使用メモリ | 52,596 KB |
最終ジャッジ日時 | 2024-11-07 08:26:55 |
合計ジャッジ時間 | 11,650 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF = 1000000000;const long long INF2 = 1000000000000000;pair<long long, long long> comp(pair<long long, long long> P, pair<long long, long long> Q){return make_pair(P.first + Q.first, max(P.second + Q.first, Q.second));}struct dual_segment_tree{int N;vector<pair<long long, long long>> ST;dual_segment_tree(){}dual_segment_tree(int n){N = 1;while (N < n){N *= 2;}ST = vector<pair<long long, long long>>(N * 2 - 1, make_pair(0, 0));}long long operator [](int k){k += N - 1;pair<long long, long long> ans = ST[k];while (k > 0){k = (k - 1) / 2;ans = comp(ans, ST[k]);}return max(ans.first, ans.second);}void range_apply(int L, int R, pair<long long, long long> P, int i, int l, int r){if (r <= L || R <= l){return;} else if (L <= l && r <= R){ST[i] = comp(ST[i], P);} else {ST[i * 2 + 1] = comp(ST[i * 2 + 1], ST[i]);ST[i * 2 + 2] = comp(ST[i * 2 + 2], ST[i]);ST[i] = make_pair(0, 0);int m = (l + r) / 2;range_apply(L, R, P, i * 2 + 1, l, m);range_apply(L, R, P, i * 2 + 2, m, r);}}void range_chmax(int L, int R, long long x){range_apply(L, R, make_pair(0, x), 0, 0, N);}void range_add(int L, int R, long long x){range_apply(L, R, make_pair(x, 0), 0, 0, N);}};int main(){int N;cin >> N;vector<int> A(N), H(N), C(N);A[0] = 0;for (int i = 1; i < N; i++){cin >> A[i];A[i]--;}for (int i = 0; i < N; i++){cin >> H[i];}for (int i = 0; i < N; i++){cin >> C[i];}vector<vector<int>> c(N);for (int i = 1; i < N; i++){c[A[i]].push_back(i);}vector<int> sz(N, 1);for (int i = N - 1; i >= 1; i--){sz[A[i]] += sz[i];}for (int i = 0; i < N; i++){for (int &j : c[i]){if (sz[j] > sz[c[i][0]]){swap(j, c[i][0]);}}}vector<int> next(N, 0);for (int i = 1; i < N; i++){if (i == c[A[i]][0]){next[i] = next[A[i]];} else {next[i] = i;}}vector<vector<int>> r(N);for (int i = 0; i < N; i++){if (next[i] == i){queue<int> Q;Q.push(i);while (!Q.empty()){int v = Q.front();Q.pop();r[i].push_back(H[v]);for (int w : c[v]){Q.push(w);}}r[i].push_back(INF);sort(r[i].begin(), r[i].end());r[i].erase(unique(r[i].begin(), r[i].end()), r[i].end());}}vector<dual_segment_tree> dp(N);for (int i = 0; i < N; i++){if (!r[i].empty()){dp[i] = dual_segment_tree(r[i].size());}}for (int i = N - 1; i >= 0; i--){int d = c[i].size();for (int j = 1; j < d; j++){int p = next[i];int v = c[i][j];int cnt = r[v].size();for (int k = 0; k < cnt; k++){int L, R;if (k == 0){L = 0;} else {L = lower_bound(r[p].begin(), r[p].end(), r[v][k - 1]) - r[p].begin() + 1;}R = lower_bound(r[p].begin(), r[p].end(), r[v][k]) - r[p].begin();dp[p].range_add(L, R + 1, dp[v][k]);}}int id = lower_bound(r[next[i]].begin(), r[next[i]].end(), H[i]) - r[next[i]].begin();dp[next[i]].range_chmax(0, id + 1, dp[next[i]][id] + C[i]);}cout << dp[0][0] << endl;}