Submission #915099

#TimeUsernameProblemLanguageResultExecution timeMemory
915099RaresFelixFireworks (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(int w) { sort(all(V)); deque<int> 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<int> 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; } int ev(int i) { ll val = ct; for(auto it : V) val += abs(it - i); return val; } }; struct tree { int n; int limExp; vi par; vector<vector<ii> > L, G; tree(int N, int LimExpl) : n(N), limExp(LimExpl), par(N), L(N), G(N) {} void add_edge(int u, int v, int w) { L[u].push_back({v, w}); L[v].push_back({u, w}); } void init() { function<fun(int, int)> dfs = [&](int u, int 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; } // printf("Pt nodul %d functia arata: \n ", u); // for(int i = 0; i <= 20; ++i) { // cout << re.ev(i) << " "; // } // printf("\nsuma fiilor:"); // for(int i = 0; i <= 20; ++i) // cout << opt[i] << " "; // cout << "\n"; return re; }; cout << dfs(0, -1).eval() / 2 << "\n"; } }; int main() { // cin.tie(0); // ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; tree T(n + m, n); for(int i = 1; i < n + m; ++i) { int 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:112:16: warning: unused variable 'v' [-Wunused-variable]
  112 |         int 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...