QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#300407 | #7501. Simple Game | defyers# | WA | 1ms | 3984kb | C++17 | 1.5kb | 2024-01-08 10:45:21 | 2024-01-08 10:45:21 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using LL = long long;
using pii = pair<int, int>;
struct edge {
int v, l, c;
};
int n, m;
vector<edge> v[5005];
vector<pair<int, int>> dp[5005];
int robot[5005];
void dfs(int x) {
for (int i = 0; i <= robot[x]; i++) {
dp[x].push_back({i, 0});
}
if (!v[x].size()) {
return;
}
for (auto i : v[x]) {
dfs(i.v);
unordered_map<int, int> M;
for (auto j : dp[i.v]) {
if (j.first % 2 != i.c) continue;
for (auto k : dp[x]) {
int num = k.first + j.first;
int cost = k.second + j.second + abs(j.first) * j.second;
if (M.find(num) != M.end()) {
M[num] = min(M[num], cost);
}
else M[num] = cost;
}
}
dp[x].clear();
for (auto j : M) {
dp[x].push_back({j.first, j.second});
}
}
}
void solve(int TC) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
dp[i].clear();
v[i].clear();
robot[i] = 0;
}
for (int i = 1; i < n; i++) {
int r1, r2, r3, r4;
v[r1].push_back({r2, r3, r4});
}
for (int i = 1; i <= m; i++) {
int r1;
cin >> r1;
robot[r1]++;
}
dfs(1);
int mn = 1e9;
for (auto i : dp[1]) {
if (i.first >= 0) mn = min(mn, i.second);
}
if (mn == 1e9) cout << "-1\n";
else cout << mn << "\n";
return;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(10);
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++) {
solve(i);
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3984kb
input:
4 2 1 4 2 1 3 1 1 4 5 1 4 4 1 9 4 9 1 0 0 1 7 3 1 4 1 5 9 2 6 5 3 5 8 9 8
output:
0 0 0 0
result:
wrong answer 1st numbers differ - expected: '5', found: '0'