QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #663469 | #8138. Alice and Her Lost Cat | Liuhao | WA | 0ms | 3844kb | C++23 | 3.1kb | 2024-10-21 15:45:22 | 2024-10-21 15:45:23 |
Judging History
answer
//
// Created by liuhao on 2024/10/21.
//
// /## /## /## /###### /## /##
// | ## |__/ | ## /##__ ## | ## | ##
// | ## /## /## /## | ####### /###### /###### |__/ \ ## | ## | ##
// | ## | ## | ## | ## | ##__ ## |____ ## /##__ ## /######/ | ########
// | ## | ## | ## | ## | ## \ ## /####### | ## \ ## /##____/ |_____ ##
// | ## | ## | ## | ## | ## | ## /##__ ## | ## | ## | ## | ##
// | ## | ## | ######/ | ## | ## | ####### | ######/ | ######## | ##
// |__/ |__/ \______/ |__/ |__/ \_______/ \______/ |________/ |__/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using i64 = long long;
using i128 = __int128;
#define PII pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N = 2010;
int dp[N][N][3];
const int inf = 1e18;
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= 2; k++) {
dp[i][j][k] = inf;
}
}
}
vector<int> a(n + 1);
vector<int> b(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
vector<vector<int>> g(n + 1);
vector<int> size(n + 1);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
auto dfs = [&](auto &&self, int u, int fa) -> void {
if ((g[u].size() == 1 && u != 1) || g[u].size() == 0) {
size[u]++;
dp[u][1][0] = a[u];
dp[u][1][1] = 0;
dp[u][1][2] = 0;
} else {
dp[u][0][0] = 0;
dp[u][0][1] = 0;
dp[u][0][2] = 0;
}
for (auto v: g[u]) {
if (v == fa)continue;
self(self, v, u);
vector ndp(size[u] + size[v] + 1, vector(3, inf));
for (int i = 0; i <= size[u]; i++) {
for (int j = 0; j <= size[v]; j++) {
ndp[i + j][0] = min(ndp[i + j][0], dp[u][i][0] + dp[v][j][0]);
ndp[i + j][1] = min({ndp[i + j][1], dp[u][i][0] + dp[v][j][1], dp[u][i][1] + dp[v][j][0]});
ndp[i + j][2] = min(ndp[i + j][2],
min({dp[u][i][0], dp[u][i][1],dp[u][i][2]}) + min(dp[v][j][0], dp[v][j][1]));
}
}
// if(u==3&&v==7){
// cout<<ndp[3][2]<<endl;
// }
for (int i = 0; i <= size[u] + size[v]; i++) {
dp[u][i][0] = ndp[i][0];
dp[u][i][1] = ndp[i][1];
dp[u][i][2] = ndp[i][2];
}
size[u] += size[v];
}
for (int i = 0; i <= size[u]; i++) {
dp[u][i][0] = min(dp[u][i][0], dp[u][i][2] + a[u]);
}
};
dfs(dfs, 1, 0);
// for(auto i:g[3]){
// if(i==2)continue;
// cout<<i<<' '<<dp[i][1][1]<<endl;
// }
int ans = 1e18;
for (int i = 1; i <= size[1]; i++) {
ans = min(ans, min(dp[1][i][0], dp[1][i][1]) + b[size[1] - i]);
}
cout << ans << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
2 8 4 2 5 2 4 2 3 2 5 5 6 7 8 9 10 13 1 2 2 3 1 4 1 5 4 6 3 7 5 8 8 4 2 3 3 2 4 4 3 4 6 8 8 9 9 14 17 1 2 2 3 3 4 3 5 4 6 3 7 3 8
output:
4 3
result:
ok 2 number(s): "4 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 1 10 5 3 2 1 4 1 2 3 1 2 2 3 10 2 1 4 3 5 6 7 8 9 3 1 1 2 3 4 5 6 7 8 8 1 2 2 3 1 4 1 5 5 6 4 7 1 8 1 9 7 10
output:
0 0 2
result:
ok 3 number(s): "0 0 2"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3648kb
input:
5 10 1 1 3 4 4 2 3 3 3 1 4 4 7 9 17 17 19 19 19 20 1 2 2 3 1 4 2 5 1 6 3 7 1 8 2 9 2 10 10 2 3 3 3 4 1 3 3 1 3 2 4 5 6 9 10 12 15 19 20 1 2 2 3 2 4 1 5 5 6 6 7 7 8 1 9 5 10 10 3 3 3 3 3 3 1 4 2 3 1 4 10 10 14 15 16 17 18 20 1 2 1 3 3 4 1 5 2 6 4 7 6 8 2 9 3 10 10 1 2 1 3 2 3 1 2 1 2 1 1 2 3 4 5 9 9 ...
output:
2 5 6 2 2
result:
wrong answer 3rd numbers differ - expected: '5', found: '6'