QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#629271 | #7502. Painting the Roads | dspt | RE | 122ms | 210956kb | C++23 | 1.5kb | 2024-10-11 10:10:42 | 2024-10-11 10:10:42 |
Judging History
answer
#include <tuple>
#include <vector>
#include <stdio.h>
using namespace std;
vector<tuple<int, int, int>> e[5001];
int c[20001], s[10001], g[5001][20001];
#define h(i) c[i + 10000]
#define f(i, j) g[i][j + 10000]
int abs(const int p) { return p > 0 ? p : -p; }
void DFS(const int p, const int f)
{
f(p, 0) = s[p] = 0;
for (auto [i, w, a] : e[p]) if (i ^ f)
{
DFS(i, p);
for (int j(-s[p] - s[i]); j <= s[p] + s[i]; ++j) h(j) = 1e9;
for (int j(-s[p]); j <= s[p]; ++j) for (int k(-s[i]); k <= s[i]; ++k)
if (a && k & 1 || !a && ~k & 1)
h(j + k) = min(h(j + k), f(p, j) + f(i, k) + abs(k) * w);
s[p] += s[i]; for (int j(-s[p]); j <= s[p]; ++j) f(p, j) = h(j);
}
for (int j(-s[p] - c[p] - 1); j <= s[p] + c[p] + 1; ++j) h(j) = 1e9;
for (int j(-s[p]); j <= s[p]; ++j) h(j + c[p]) = f(p, j);
int w(1e9); s[p] += c[p] + 1; for (int j(s[p]); j >= -s[p]; --j) f(p, j) = w = min(w, h(j));
}
int main()
{
int t; scanf("%d", &t);
while (t--)
{
int n, m; scanf("%d%d", &n, &m);
for (int i(1), u, v, w, a; i < n; ++i)
{
scanf("%d%d%d%d", &u, &v, &w, &a);
e[u].emplace_back(v, w, a); e[v].emplace_back(u, w, a);
}
while (m--) { int u; scanf("%d", &u); ++c[u]; }
DFS(1, 0);
printf("%d\n", f(1, 0) < 1e9 ? f(1, 0) : -1);
for (int i(1); i <= n; ++i) c[i] = 0, e[i].clear();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
5 3 2 1 2 1 1 2 3 2 1 1 3 4 2 1 2 3 1 2 3 1 0 3 4 4 1 1 2 5 4 1 2 3 0 2 3 1 1 3 4 2 0 4 5 2 1 1 1 1 1 5 2 1 2 2 1 1 3 3 0 1 5 2 1 3 4 1 1 1 2 10 5 1 2 10 1 2 3 3 1 3 4 4 0 4 5 4 1 5 6 2 1 2 7 8 0 2 8 9 1 4 9 1 0 1 10 4 0 10 10 2 1 8
output:
3 9 21 -1 42
result:
ok 5 number(s): "3 9 21 -1 42"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3924kb
input:
1000 5 5 1 2 4 1 2 3 9 0 3 4 10 1 3 5 8 1 1 5 2 5 1 5 3 1 2 7 1 1 3 7 0 2 4 9 0 3 5 4 1 3 4 3 5 3 1 2 7 1 2 3 1 0 1 4 7 1 4 5 5 1 4 4 3 5 1 1 2 3 1 1 3 6 0 2 4 10 0 2 5 7 0 1 5 3 1 2 10 1 1 3 10 0 1 4 1 1 3 5 4 0 2 5 2 5 5 1 2 7 0 1 3 5 0 2 4 8 1 2 5 10 0 2 2 3 5 4 5 4 1 2 6 1 1 3 4 0 3 4 4 0 1 5 5 ...
output:
22 -1 19 3 11 8 11 7 8 0 10 1 1 7 5 28 12 -1 19 16 12 13 -1 32 9 18 16 14 10 12 16 0 11 -1 17 -1 9 14 27 8 11 -1 6 6 15 18 46 0 14 9 -1 5 8 22 -1 -1 17 -1 25 6 0 24 6 15 21 15 22 -1 6 0 65 20 5 28 20 0 20 19 18 -1 10 0 16 9 19 6 21 11 11 4 6 20 11 0 8 8 31 8 23 -1 8 -1 11 -1 9 13 -1 -1 19 9 20 19 6 ...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 4032kb
input:
250 20 10 1 2 10 1 1 3 3 1 2 4 6 0 4 5 8 0 2 6 5 0 4 7 1 1 1 8 6 0 4 9 2 1 3 10 9 1 3 11 1 0 6 12 10 0 6 13 8 0 13 14 7 0 14 15 10 1 1 16 4 0 12 17 2 0 17 18 8 1 18 19 3 0 2 20 4 1 15 14 20 20 9 17 4 4 13 13 20 6 1 2 4 1 1 3 10 1 2 4 10 1 3 5 1 1 2 6 6 0 4 7 5 1 3 8 8 1 7 9 7 0 6 10 3 1 6 11 4 1 8 1...
output:
47 -1 84 68 61 112 39 -1 -1 48 71 -1 -1 77 -1 -1 59 97 -1 -1 74 52 -1 -1 -1 84 48 -1 68 60 57 -1 79 68 -1 79 51 -1 33 48 62 -1 -1 113 84 44 -1 79 -1 76 64 -1 -1 110 42 40 56 81 -1 73 68 -1 74 125 67 44 -1 103 -1 -1 -1 89 64 -1 85 -1 50 -1 64 -1 -1 94 46 75 -1 -1 -1 101 67 61 -1 -1 18 100 57 102 -1 -...
result:
ok 250 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 8044kb
input:
100 50 43 1 2 7 1 1 3 5 0 2 4 9 0 1 5 8 0 2 6 5 1 6 7 8 1 1 8 10 0 5 9 2 1 1 10 4 0 2 11 3 0 11 12 6 0 2 13 9 1 7 14 5 0 12 15 7 0 2 16 5 0 15 17 4 1 1 18 6 1 16 19 5 1 5 20 7 1 10 21 6 1 14 22 2 0 14 23 3 1 18 24 2 1 22 25 8 1 12 26 6 0 5 27 1 0 21 28 1 1 27 29 9 1 25 30 7 0 22 31 9 0 9 32 7 0 26 3...
output:
149 233 -1 204 -1 145 164 -1 -1 -1 185 182 -1 145 252 -1 -1 160 186 163 -1 256 182 173 202 238 410 -1 169 -1 259 -1 103 117 171 -1 -1 -1 163 -1 -1 265 -1 -1 -1 162 136 140 -1 -1 217 211 193 114 246 251 133 176 -1 -1 219 139 195 -1 214 180 -1 223 132 153 -1 -1 -1 172 310 102 -1 200 -1 -1 195 -1 -1 20...
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 23ms
memory: 42884kb
input:
10 500 815 1 2 8 1 1 3 1 0 1 4 4 1 4 5 5 0 4 6 8 0 3 7 7 0 5 8 2 1 4 9 9 1 2 10 9 1 1 11 3 1 1 12 9 0 2 13 2 0 5 14 1 1 3 15 1 1 3 16 4 0 5 17 8 0 4 18 9 0 4 19 4 0 2 20 7 0 4 21 7 1 5 22 9 1 2 23 10 1 3 24 7 0 1 25 7 0 1 26 2 0 4 27 4 1 1 28 9 0 3 29 3 1 2 30 6 0 3 31 10 1 1 32 3 1 1 33 2 1 3 34 2 ...
output:
1335 2129 1372 1752 1354 1809 1309 1542 1359 -1
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 20ms
memory: 42912kb
input:
10 500 129 1 2 7 1 1 3 7 1 1 4 4 1 4 5 6 1 3 6 10 0 3 7 9 0 7 8 2 0 4 9 2 1 2 10 2 0 6 11 10 0 2 12 7 0 6 13 10 0 10 14 1 1 6 15 9 0 15 16 1 0 3 17 8 1 13 18 7 0 8 19 9 1 9 20 2 1 9 21 5 0 1 22 10 0 16 23 1 0 6 24 7 1 14 25 10 0 15 26 4 1 23 27 2 1 24 28 9 0 23 29 5 1 17 30 8 0 10 31 7 1 31 32 4 0 3...
output:
-1 1604 -1 -1 1375 1450 -1 1448 1350 1366
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 24ms
memory: 44880kb
input:
10 500 781 1 2 3 1 2 3 7 1 1 4 2 0 3 5 2 0 3 6 4 0 2 7 7 1 4 8 2 1 5 9 6 1 4 10 2 1 2 11 3 0 4 12 6 0 4 13 8 0 1 14 2 1 3 15 8 0 1 16 7 1 1 17 10 1 4 18 3 0 3 19 3 0 4 20 1 0 4 21 9 1 5 22 10 0 2 23 9 0 2 24 4 1 4 25 3 1 1 26 9 0 5 27 1 0 2 28 9 0 4 29 6 0 5 30 1 1 1 31 1 0 2 32 2 0 4 33 2 0 1 34 5 ...
output:
1433 -1 1365 -1 1425 2849 1360 1571 1369 1666
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 64ms
memory: 187392kb
input:
2 2500 1102 1 2 2 0 1 3 2 1 2 4 5 0 4 5 9 0 4 6 3 1 3 7 4 0 1 8 9 0 4 9 9 0 5 10 10 1 1 11 10 0 5 12 1 1 5 13 7 0 4 14 10 1 3 15 3 1 4 16 3 1 4 17 9 0 5 18 9 0 2 19 10 1 1 20 8 0 3 21 6 0 1 22 2 1 1 23 8 0 2 24 7 0 5 25 8 0 4 26 1 1 3 27 2 0 4 28 3 0 1 29 4 0 2 30 6 0 5 31 5 0 3 32 2 0 5 33 9 0 5 34...
output:
-1 -1
result:
ok 2 number(s): "-1 -1"
Test #9:
score: 0
Accepted
time: 114ms
memory: 183684kb
input:
2 2500 2299 1 2 9 0 2 3 1 0 3 4 9 1 3 5 10 1 5 6 8 0 2 7 10 1 5 8 10 0 1 9 6 0 1 10 1 0 1 11 6 0 2 12 10 0 5 13 3 0 3 14 5 0 5 15 1 1 4 16 10 0 2 17 4 1 3 18 3 0 4 19 2 0 4 20 4 0 2 21 6 1 1 22 10 0 4 23 8 0 3 24 10 1 1 25 10 1 5 26 5 1 5 27 1 1 1 28 2 0 3 29 2 0 1 30 9 0 5 31 2 1 2 32 6 1 4 33 1 1 ...
output:
6761 8789
result:
ok 2 number(s): "6761 8789"
Test #10:
score: 0
Accepted
time: 122ms
memory: 170260kb
input:
2 2500 4206 1 2 7 1 1 3 3 0 2 4 10 0 4 5 3 1 3 6 8 1 3 7 10 0 3 8 7 0 1 9 5 0 5 10 4 0 1 11 1 0 3 12 9 0 2 13 2 1 2 14 3 1 4 15 6 0 1 16 1 1 3 17 1 1 5 18 6 0 3 19 7 1 2 20 1 1 4 21 10 1 2 22 4 0 1 23 6 0 5 24 10 0 1 25 6 1 2 26 5 0 3 27 5 1 1 28 9 0 2 29 9 0 3 30 9 0 3 31 7 1 5 32 10 0 2 33 7 0 1 3...
output:
6858 -1
result:
ok 2 number(s): "6858 -1"
Test #11:
score: 0
Accepted
time: 112ms
memory: 187528kb
input:
2 2500 1884 1 2 7 1 2 3 5 0 3 4 4 1 4 5 9 0 1 6 6 1 3 7 1 1 5 8 9 1 1 9 1 0 3 10 5 1 1 11 5 1 3 12 9 1 4 13 4 1 3 14 2 1 5 15 10 1 1 16 10 0 5 17 5 1 4 18 1 0 2 19 6 1 3 20 8 0 1 21 1 0 1 22 2 1 4 23 6 0 3 24 5 0 4 25 2 0 4 26 7 0 5 27 4 0 3 28 4 1 5 29 1 1 2 30 7 1 4 31 8 1 3 32 8 0 3 33 2 1 2 34 6...
output:
6616 7292
result:
ok 2 number(s): "6616 7292"
Test #12:
score: 0
Accepted
time: 118ms
memory: 210956kb
input:
1 5000 2092 1 2 6 0 1 3 3 1 1 4 10 0 4 5 10 1 4 6 3 1 6 7 5 1 7 8 4 0 7 9 3 1 7 10 10 1 10 11 4 1 7 12 1 0 12 13 5 0 9 14 1 0 10 15 1 1 14 16 2 0 15 17 7 1 13 18 9 1 14 19 8 0 17 20 10 1 16 21 2 1 21 22 6 1 22 23 1 1 21 24 4 0 23 25 5 1 25 26 2 0 25 27 10 1 25 28 8 1 28 29 8 1 27 30 9 0 26 31 3 0 31...
output:
18174
result:
ok 1 number(s): "18174"
Test #13:
score: -100
Runtime Error
input:
1 5000 1616 1 2 3 1 1 3 4 0 3 4 2 0 3 5 4 0 4 6 5 0 4 7 4 0 3 8 1 0 5 9 2 0 3 10 5 0 1 11 5 1 4 12 2 0 3 13 2 1 4 14 5 0 4 15 4 0 1 16 1 0 1 17 5 0 4 18 6 0 4 19 4 0 4 20 5 0 2 21 2 0 1 22 6 1 3 23 4 0 2 24 4 1 3 25 8 0 4 26 2 1 4 27 6 0 2 28 7 1 2 29 1 1 1 30 9 1 1 31 7 0 1 32 4 0 4 33 5 0 5 34 6 0...