Submission #915101

#TimeUsernameProblemLanguageResultExecution timeMemory
915101RaresFelixFireworks (APIO16_fireworks)C++17
7 / 100
1 ms348 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("O3") //#pragma GCC target("avx,avx2,fma") #define sz(x) int((x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; using ll = long long; using ld = long double; // or double, if TL is tight using str = string; using ii = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vll = vector<ll>; struct fun { ll ct = 0; vll V; fun &operator+=(const fun &rhs) { ct += rhs.ct; for(auto it : rhs.V) V.push_back(it); return *this; } fun clean(ll w) { sort(all(V)); deque<ll> D; for(auto it : V) D.push_back(it); V.clear(); while(D.size() > 2) { ct += D.back() - D.front(); D.pop_back(); D.pop_front(); } for(auto it : D) V.push_back(it + w); if(V.size() == 1) V.push_back(V.back()); return *this; } ll eval() { sort(all(V)); deque<ll> D; for(auto it : V) D.push_back(it); V.clear(); while(!D.empty()) { ct += D.back() - D.front(); D.pop_back(); if(!D.empty()) D.pop_front(); } return ct; } ll ev(ll i) { ll val = ct; for(auto it : V) val += abs(it - i); return val; } }; struct tree { ll n; ll limExp; vi par; vector<vector<ii> > L, G; tree(ll N, ll LimExpl) : n(N), limExp(LimExpl), par(N), L(N), G(N) {} void add_edge(ll u, ll v, ll w) { L[u].push_back({v, w}); L[v].push_back({u, w}); } void init() { function<fun(ll, ll)> dfs = [&](ll u, ll p) { if(u >= limExp) { /// frunza cu bomba, nu face nimic fun re; re.V.push_back(0); re.V.push_back(0); return re; } fun re; for(auto [it, w] : L[u]) if(it != p) { auto fiu = dfs(it, u).clean(w); re += fiu; } return re; }; ll re = dfs(0, -1).eval(); assert(re % 2 == 0); cout << re / 2 << "\n"; } }; int main() { cin.tie(0); ios_base::sync_with_stdio(0); ll n, m; cin >> n >> m; tree T(n + m, n); for(ll i = 1; i < n + m; ++i) { ll u, v, w; cin >> u >> w; --u; T.add_edge(u, i, w); } T.init(); return 0; }

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:106:15: warning: unused variable 'v' [-Wunused-variable]
  106 |         ll u, v, w;
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...