제출 #705123

#제출 시각아이디문제언어결과실행 시간메모리
705123600MihneaFireworks (APIO16_fireworks)C++17
7 / 100
1 ms340 KiB
#include <cmath> #include <functional> #include <fstream> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <cassert> #include <bitset> #include <sstream> #include <chrono> #include <cstring> #include <numeric> using namespace std; #define int long long const int INF = (int)1e18 + 7; multiset<int> inc(multiset<int> s, int by) { multiset<int> ret; for (auto& x : s) { ret.insert(x + by); } return ret; } void baga(multiset<int>& s, int& sol, int x, int y) { if (s.empty()) { s.insert(x); s.insert(y); return; } vector<int> vls; for (auto& v : s) { vls.push_back(v); } s.insert(x); s.insert(y); vector<int> opts; assert((int)vls.size() % 2 == 0); int l1 = x, r1 = y; assert(l1 <= r1); int l2 = vls[(int)vls.size() / 2 - 1], r2 = vls[(int)vls.size() / 2]; assert(l2 <= r2); int lmax = max(l1, l2); int rmin = min(r1, r2); if (lmax <= rmin) { return; } else { if (r1 < l2) { sol += l2 - r1; } else { assert(r2 < l1); sol += l1 - r2; } } } void print(multiset<int> s) { cout << " ---> "; for (auto& x : s) { cout << x << " "; } cout << "\n"; } signed main() { #ifdef ONPC FILE* stream; freopen_s(&stream, "input.txt", "r", stdin); #else ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #endif if (0) { int sol = 0; multiset<int> s; baga(s, sol, 2, 2); cout << sol << "\n"; baga(s, sol, 1, 1); cout << sol << "\n"; exit(0); } int n1, n2, n; cin >> n1 >> n2; n = n1 + n2; vector<vector<int>> g(n); vector<int> sub(n, 0); vector<int> par(n, 0), c(n, 0); for (int i = 1; i < n; i++) { cin >> par[i] >> c[i]; par[i]--; assert(0 <= par[i] && par[i] < i); g[par[i]].push_back(i); } vector<int> dp(n, 0); vector<multiset<int>> s(n); for (int i = 0; i < n; i++) { sub[i] = (i >= n1); } for (int i = n - 1; i >= 0; i--) { for (auto& j : g[i]) { sub[i] += sub[j]; } if (i >= n1) { assert(sub[i] == 1); } } int sol = 0; for (int i = n - 1; i >= 0; i--) { int have = 0; for (auto& i : g[i]) { have += (sub[i] > 0); } if (i >= n1) { dp[i] = 0; s[i].insert(0); s[i].insert(0); } else { assert(have >= 1); if (have == 1) { int nr = 0; for (auto& j : g[i]) { if (sub[j]) { nr++; assert(s[i].empty()); s[i] = s[j]; dp[i] = dp[j]; } } assert(!s[i].empty()); assert(nr == 1); assert(nr == have); } else { s[i].clear(); for (auto& j : g[i]) { if (sub[j]) { //if (i == 3) //{ // print(s[j]); //} dp[i] += dp[j]; assert((int)s[j].size() == 2); vector<int> vls; for (auto& vl : s[j]) { vls.push_back(vl); } assert((int)vls.size() == 2); baga(s[i], dp[i], vls[0], vls[1]); } } } } assert((int)s[i].size() % 2 == 0); assert((int)s[i].size() == 2 || (int)s[i].size() >= 4); if ((int)s[i].size() >= 2) { vector<int> vals; for (auto& x : s[i]) { vals.push_back(x); } int d = (int)vals.size() / 2; s[i].clear(); s[i].insert(vals[d / 2]); s[i].insert(vals[d / 2 + 1]); } s[i] = inc(s[i], c[i]); assert((int)s[i].size() == 2); } /*for (int i = 0; i < n; i++) { cout << i << ", " << dp[i] << " : "; print(s[i]); }*/ cout << dp[0] << "\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

fireworks.cpp: In function 'int main()':
fireworks.cpp:144:6: warning: unused variable 'sol' [-Wunused-variable]
  144 |  int sol = 0;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...