QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#629271#7502. Painting the RoadsdsptRE 122ms210956kbC++231.5kb2024-10-11 10:10:422024-10-11 10:10:42

Judging History

你现在查看的是最新测评结果

  • [2024-10-11 10:10:42]
  • 评测
  • 测评结果：RE
  • 用时：122ms
  • 内存：210956kb
查看
  • [2024-10-11 10:10:42]
  • 提交

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;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

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...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-03 22:27:05 | OpenSource Project