Submission #288596

#TimeUsernameProblemLanguageResultExecution timeMemory
288596dlwocks31Magic Tree (CEOI19_magictree)C++17
58 / 100
190 ms32376 KiB
#include <bits/stdc++.h> using namespace std; #define int long long template<typename T> int SIZE(T (&t)){ return t.size(); } template<typename T, size_t N> int SIZE(T (&t)[N]){ return N; } string to_string(char t){ return "'" + string({t}) + "'"; } string to_string(bool t){ return t ? "true" : "false"; } string to_string(const string &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += t[i]; } return '"' + ret + '"'; } string to_string(const char* t){ string ret(t); return to_string(ret); } template<size_t N> string to_string(const bitset<N> &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){ ret += t[i] + '0'; } return to_string(ret); } template<typename T, typename... Coords> string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C); template<typename T, typename S> string to_string(const pair<T, S> &t){ return "(" + to_string(t.first) + ", " + to_string(t.second) + ")"; } template<typename T, typename... Coords> string to_string(const T (&t), int x1, int x2, Coords... C){ string ret = "["; x1 = min(x1, SIZE(t)); auto e = begin(t); advance(e,x1); for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += to_string(*e, C...) + (i != _i ? ", " : ""); e = next(e); } return ret + "]"; } template<int Index, typename... Ts> struct print_tuple{ string operator() (const tuple<Ts...>& t) { string ret = print_tuple<Index - 1, Ts...>{}(t); ret += (Index ? ", " : ""); return ret + to_string(get<Index>(t)); } }; template<typename... Ts> struct print_tuple<0, Ts...> { string operator() (const tuple<Ts...>& t) { return to_string(get<0>(t)); } }; template<typename... Ts> string to_string(const tuple<Ts...>& t) { const auto Size = tuple_size<tuple<Ts...>>::value; return print_tuple<Size - 1, Ts...>{}(t); } void dbgr(){;} template<typename Heads, typename... Tails> void dbgr(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgr(T...); } void dbgs(){;} template<typename Heads, typename... Tails> void dbgs(Heads H, Tails... T){ cout << H << " "; dbgs(T...); } #define dbgv(...) cout << to_string(__VA_ARGS__) << endl; #define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__); const int MX = 1e5+1; vector<int> adj[MX]; pair<int, int> fruit[MX]; multiset<pair<int, int>> ms[MX]; void merge(multiset<pair<int, int>>& st, pair<int, int> pr) { auto [d, w] = pr; auto it = st.lower_bound(make_pair(d+1, -1)); while(w > 0 && it != st.end()) { if(w >= it->second) { it = st.erase(it); w -= it->second; } else { st.insert({it->first, it->second - w}); st.erase(it); w = 0; break; } } st.insert(pr); } void dfs(int i, int p) { int leaf = 1; for(int a: adj[i]) { if(a == p) continue; leaf = 0; dfs(a, i); } if(leaf) { if(fruit[i].first) ms[i] = {fruit[i]}; } else { int mx = 0; for(int a: adj[i]) { if(a == p) continue; if(ms[a].size() > ms[mx].size()) mx = a; } ms[i] = move(ms[mx]); for(int a: adj[i]) { if(a == p || a == mx) continue; for(auto pr: ms[a]) { ms[i].insert(pr); } ms[a].clear(); } if(fruit[i].first) merge(ms[i], fruit[i]); } } int32_t main() { ios::sync_with_stdio(0);cin.tie(0); int n, m, k; cin >> n >> m >> k; for(int i=2; i<=n; i++) { int p; cin >> p; adj[p].push_back(i); adj[i].push_back(p); } for(int i=0; i<m; i++) { int v, d, w; cin >> v >> d >> w; fruit[v] = {d, w}; } dfs(1, 0); int ans = 0; for(auto [d, w]: ms[1]) { ans += w; } cout << ans; }
#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...