제출 #1124052

#제출 시각아이디문제언어결과실행 시간메모리
1124052math_rabbit_1028트리 (IOI24_tree)C++20
10 / 100
2096 ms38508 KiB
#include "tree.h" #include <queue> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; int n; int par[202020]; vector<int> child[202020]; ll w[202020]; void init(vector<int> P, vector<int> W) { n = (int)P.size(); for (int i = 0; i < n; i++) { par[i] = P[i]; child[par[i]].push_back(i); } for (int i = 0; i < n; i++) w[i] = W[i]; } ll dp[202020], sum[202020]; ll minabs(ll l, ll r) { if (l <= 0 && r >= 0) return 0; if (r < 0) return r; if (l > 0) return l; } typedef priority_queue<pll, vector<pll>, greater<pll>> pq; pq solve(int v, ll L, ll R) { pq plus; if (child[v].size() == 0) { dp[v] += L * w[v]; sum[v] = L; return plus; } for (int u : child[v]) { pq t = solve(u, L, R); if (plus.size() < t.size()) swap(plus, t); while (!t.empty()) { plus.push(t.top()); t.pop(); } dp[v] += dp[u]; sum[v] += sum[u]; } plus.push({w[v], sum[v]-L}); while (sum[v] > R) { pll t = plus.top(); plus.pop(); if (sum[v] - R < t.second) { dp[v] += (sum[v] - R) * t.first; sum[v] -= (sum[v] - R); plus.push({t.first, t.second - (sum[v] - R)}); } else { dp[v] += t.second * t.first; sum[v] -= t.second; } } return plus; } long long query(int L, int R) { for (int i = 0; i < n; i++) sum[i] = dp[i] = 0; solve(0, L, R); return dp[0]; }

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

tree.cpp: In function 'll minabs(ll, ll)':
tree.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^
#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...