#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e3 + 25;
vector <pair <int, int>> adj[MAXN];
int dp[MAXN][301], n, m;
void dfs (int pos) {
for (auto j : adj[pos]) {
dfs(j.first);
}
if(adj[pos].empty()) {
for (int i = 1; i <= 300; i++) dp[pos][i] = 1e18;
return;
}
for (int i = 0; i <= 300; i++) {
int sum = 0;
for (auto j : adj[pos]) {
int mn = 1e18;
for(int k = 0; k <= i; k++) mn = min(mn, abs(j.second - i + k) +dp[j.first][k]);
sum += mn;
}
dp[pos][i] = sum;
}
}
signed main () {
cin >> n >> m;
n += m;
for (int i = 2; i <= n; i++) {
int x, y; cin >> x >> y;
adj[x].push_back({i, y});
}
dfs(1);
int mn = 1e18;
for (int i = 0; i <= 300; i++) mn = min(mn, dp[1][i]);
for (int i = 1; i <= n - m; i++) {
for (int j = 1; j < 300; j++) {
assert(dp[i][j] - dp[i][j - 1] <= dp[i][j + 1] - dp[i][j]);
}
}
cout << mn << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
3 ms |
604 KB |
Output is correct |
4 |
Correct |
5 ms |
604 KB |
Output is correct |
5 |
Correct |
6 ms |
600 KB |
Output is correct |
6 |
Correct |
8 ms |
2792 KB |
Output is correct |
7 |
Correct |
10 ms |
2652 KB |
Output is correct |
8 |
Correct |
9 ms |
2652 KB |
Output is correct |
9 |
Correct |
11 ms |
2648 KB |
Output is correct |
10 |
Correct |
12 ms |
856 KB |
Output is correct |
11 |
Correct |
11 ms |
1116 KB |
Output is correct |
12 |
Correct |
13 ms |
1124 KB |
Output is correct |
13 |
Correct |
13 ms |
1116 KB |
Output is correct |
14 |
Correct |
14 ms |
1288 KB |
Output is correct |
15 |
Correct |
15 ms |
1112 KB |
Output is correct |
16 |
Correct |
15 ms |
1116 KB |
Output is correct |
17 |
Correct |
14 ms |
1116 KB |
Output is correct |
18 |
Correct |
14 ms |
1236 KB |
Output is correct |
19 |
Correct |
14 ms |
1264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |