제출 #705072

#제출 시각아이디문제언어결과실행 시간메모리
705072600MihneaFireworks (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; struct T { int opt; vector<int> lens; }; vector<int> inc(vector<int> a, int by) { for (auto& x : a) { x += by; } return a; } 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 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); } 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); } } vector<T> dp(n); int sol = 0; for (int i = n - 1; i >= 0; i--) { for (auto& j : g[i]) { // cout << i << " " << j << " " << c[j] << "\n"; } int have = 0; for (auto& i : g[i]) { have += (sub[i] > 0); } if (i >= n1) { dp[i] = { 0, {0} }; } else { assert(have >= 1); if (have == 1) { int nr = 0; for (auto& j : g[i]) { if (sub[j]) { nr++; dp[i] = { dp[j].opt, dp[j].lens }; } } assert(nr == 1); assert(nr == have); } else { dp[i].opt = 0; vector<vector<int>> lens; for (auto& j : g[i]) { if (sub[j]) { dp[i].opt += dp[j].opt; lens.push_back(dp[j].lens); } } assert((int)lens.size() == have); assert((int)lens.size() >= 2); vector<int> all_lens; for (auto& v : lens) { for (auto& l : v) { all_lens.push_back(l); } } sort(all_lens.begin(), all_lens.end()); all_lens.resize(unique(all_lens.begin(), all_lens.end()) - all_lens.begin()); int best = INF; vector<int> posi; for (auto& the_len : all_lens) { int cur = 0; for (auto& v : lens) { assert((int)v.size() == 1 || (int)v.size() == 2); if ((int)v.size() == 1) { cur += abs(v[0]-the_len); } else { cur += min(abs(v[0] - the_len), abs(v[1] - the_len)); } } if (cur < best) { best = cur; posi.clear(); } if (cur == best) { posi.push_back(the_len); } } assert((int)posi.size() == 1 || (int)posi.size() == 2); dp[i].opt += best; dp[i].lens = posi; //int init = sol; //vector<int> los; //for (auto& j : g[i]) //{ // if (sub[j]) // { // los.push_back(c[j] + le[j]); // } //} //assert((int)los.size() == have); //sort(los.begin(), los.end()); //assert((int)los.size() >= 2); //int p = (int)los.size() / 2; //for (int j = 0; j < (int)los.size(); j++) //{ // sol += abs(los[j] - los[p]); //} //int delta = sol - init; //if (delta > 0) //{ // cout << "\t\t\t\t\t" << i << " : " << delta << ", "; // for (auto& lo : los) // { // cout << lo << " "; // } // cout << "\n"; //} } } dp[i].lens = inc(dp[i].lens, c[i]); } cout << dp[0].opt << "\n"; return 0; }

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

fireworks.cpp: In function 'int main()':
fireworks.cpp:89:14: warning: unused variable 'j' [-Wunused-variable]
   89 |   for (auto& j : g[i])
      |              ^
fireworks.cpp:86:6: warning: unused variable 'sol' [-Wunused-variable]
   86 |  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...