Submission #1210672

#TimeUsernameProblemLanguageResultExecution timeMemory
1210672trimkusTree (IOI24_tree)C++20
7 / 100
377 ms26700 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; using ll = long long; int N; vector<int> W; vector<vector<int>> adj; vector<int> P; vector<int> leave_cnt; int cnt; void init(vector<int> _P, vector<int> _W) { P = _P; P[0] = -1; W = _W; N = (int)P.size(); leave_cnt.resize(N); adj.assign(N, {}); for (int i = 1; i < N; i++) { adj[P[i]].push_back(i); adj[i].push_back(P[i]); } auto dfs = [&](auto& dfs, int v, int p) -> void { leave_cnt[v] += (adj[v].size() == 1 && v != 0); for (auto& u : adj[v]) { if (u == p) continue; dfs(dfs, u, v); leave_cnt[v] += leave_cnt[u]; } if (W[v] == 0) { int dec = max(0, leave_cnt[v] - 1); leave_cnt[v] -= dec; cnt -= dec; } if ((int)adj[v].size() == 1 && v != 0 && W[v] == 0) { cnt--; } }; dfs(dfs, 0, -1); for (int i = 1; i < N; ++i) { if ((int)adj[i].size() == 1) { cnt++; } } } long long query(int L, int R) { cerr << "Query " << L << " " << R << "\n"; ll res = 1LL * cnt * L + max(0LL, 1LL * cnt * L - R); return res; }
#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...