Submission #519736

#TimeUsernameProblemLanguageResultExecution timeMemory
519736MonarchuwuMagic Tree (CEOI19_magictree)C++17
3 / 100
232 ms388344 KiB
// nén cây và k dựa vào m // O(n * min(m, k)) #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define ff first #define ss second const int N = 1e5 + 9; int n, m, k; int p[N]; pii fruit[N]; vector<int> g[N]; namespace sub2 { bool check() { for (int i = 2; i <= n; ++i) if (g[i].size() && fruit[i].ff) return false; return true; } void solve() { ll sum(0); for (int i = 2; i <= n; ++i) sum += fruit[i].ss; cout << sum << '\n'; } } namespace sub3 { bool check() { for (int i = 2; i <= n; ++i) if (p[i] != i - 1 || fruit[i].ff > 1) return false; return true; } int lis[N]; void solve() { int cnt(0); for (int i = n, pos; i; --i) if (fruit[i].ff) { pos = upper_bound(lis + 1, lis + cnt + 1, fruit[i].ff) - lis; if (cnt < pos) cnt = pos; lis[pos] = fruit[i].ff; } cout << cnt << '\n'; } } ll dp[N][1003]; namespace sub1456 { int cnt(0), b[N]; void dfs(int u) { for (int v : g[u]) { dfs(v); for (int i = 0; i < cnt; ++i) dp[u][i] += dp[v][i]; } if (fruit[u].ff) { dp[u][fruit[u].ff] += fruit[u].ss; for (int i = fruit[u].ff + 1; i < cnt; ++i) dp[u][i] = max(dp[u][i], (ll)fruit[u].ss); } } void solve() { for (int i = 1; i <= n; ++i) if (fruit[i].ff) b[++cnt] = fruit[i].ff; sort(b + 1, b + cnt + 1); cnt = unique(b + 1, b + cnt + 1) - b; for (int i = 1; i <= n; ++i) if (fruit[i].ff) fruit[i].ff = lower_bound(b + 1, b + cnt, fruit[i].ff) - b; dfs(1); cout << *max_element(dp[1], dp[1] + cnt) << '\n'; } } int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> n >> m >> k; for (int i = 2; i <= n; ++i) { cin >> p[i]; g[p[i]].push_back(i); } for (int i = 0, v; i < m; ++i) { cin >> v; cin >> fruit[v].ff >> fruit[v].ss; } if (sub2::check()) sub2::solve(); else if (sub3::check()) sub3::solve(); else sub1456::solve(); } /** /\_/\ * (= ._.) * / >0 \>1 **/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...