QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#629286	#7502. Painting the Roads	dspt	AC ✓	241ms	241224kb	C++23	1.5kb	2024-10-11 10:17:10	2024-10-11 10:17:10

Judging History

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

[2024-10-11 10:17:10]
评测

测评结果：AC
用时：241ms
内存：241224kb

查看

[2024-10-11 10:17:10]
提交

answer

#include <tuple>
#include <vector>
#include <stdio.h>
using namespace std;
vector<tuple<int, int, int>> e[5001];
int b[5001], s[5001], c[20001], 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] - b[p] - 1); j <= s[p] + b[p] + 1; ++j) h(j) = 1e9;
    for (int j(-s[p]); j <= s[p]; ++j) h(j + b[p]) = f(p, j);
    int w(1e9); s[p] += b[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); ++b[u]; }
        DFS(1, 0); printf("%d\n", f(1, 0) < 1e9 ? f(1, 0) : -1);
        for (int i(1); i <= n; ++i) b[i] = 0, e[i].clear();
    }
    return 0;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3956kb

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:

result:

ok 5 number(s): "3 9 21 -1 42"

Test #2:

score: 0

Accepted

time: 2ms

memory: 3880kb

input:

output:

result:

ok 1000 numbers

Test #3:

score: 0

Accepted

time: 0ms

memory: 6084kb

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:

result:

ok 250 numbers

Test #4:

score: 0

Accepted

time: 4ms

memory: 8064kb

input:

output:

result:

ok 100 numbers

Test #5:

score: 0

Accepted

time: 23ms

memory: 42996kb

input:

output:

result:

ok 10 numbers

Test #6:

score: 0

Accepted

time: 23ms

memory: 43052kb

input:

output:

result:

ok 10 numbers

Test #7:

score: 0

Accepted

time: 24ms

memory: 42936kb

input:

output:

result:

ok 10 numbers

Test #8:

score: 0

Accepted

time: 63ms

memory: 199028kb

input:

output:

-1
-1

result:

ok 2 number(s): "-1 -1"

Test #9:

score: 0

Accepted

time: 107ms

memory: 200976kb

input:

output:

6761
8789

result:

ok 2 number(s): "6761 8789"

Test #10:

score: 0

Accepted

time: 124ms

memory: 199060kb

input:

output:

6858
-1

result:

ok 2 number(s): "6858 -1"

Test #11:

score: 0

Accepted

time: 119ms

memory: 199152kb

input:

output:

6616
7292

result:

ok 2 number(s): "6616 7292"

Test #12:

score: 0

Accepted

time: 108ms

memory: 221356kb

input:

output:

result:

ok 1 number(s): "18174"

Test #13:

score: 0

Accepted

time: 116ms

memory: 209140kb

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:

ok 1 number(s): "9970"

Test #14:

score: 0

Accepted

time: 93ms

memory: 216832kb

input:

output:

result:

ok 1 number(s): "5981"

Test #15:

score: 0

Accepted

time: 104ms

memory: 234060kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0

Accepted

time: 131ms

memory: 239980kb

input:

output:

result:

ok 1 number(s): "20709"

Test #17:

score: 0

Accepted

time: 189ms

memory: 241224kb

input:

output:

result:

ok 1 number(s): "14832"

Test #18:

score: 0

Accepted

time: 206ms

memory: 228600kb

input:

output:

result:

ok 1 number(s): "12769"

Test #19:

score: 0

Accepted

time: 171ms

memory: 218744kb

input:

output:

result:

ok 1 number(s): "11987"

Test #20:

score: 0

Accepted

time: 216ms

memory: 230512kb

input:

output:

result:

ok 1 number(s): "13461"

Test #21:

score: 0

Accepted

time: 163ms

memory: 240364kb

input:

output:

result:

ok 1 number(s): "15399"

Test #22:

score: 0

Accepted

time: 231ms

memory: 228572kb

input:

output:

result:

ok 1 number(s): "13750"

Test #23:

score: 0

Accepted

time: 186ms

memory: 228424kb

input:

output:

result:

ok 1 number(s): "12984"

Test #24:

score: 0

Accepted

time: 75ms

memory: 224452kb

input:

output:

result:

ok 1 number(s): "439"

Test #25:

score: 0

Accepted

time: 186ms

memory: 238620kb

input:

output:

result:

ok 1 number(s): "15533"

Test #26:

score: 0

Accepted

time: 112ms

memory: 230388kb

input:

output:

result:

ok 1 number(s): "8937"

Test #27:

score: 0

Accepted

time: 102ms

memory: 238044kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #28:

score: 0

Accepted

time: 241ms

memory: 228576kb

input:

output:

result:

ok 1 number(s): "13800"

Test #29:

score: 0

Accepted

time: 76ms

memory: 234308kb

input:

1
5000 571
1 2 7 1
1 3 9 0
1 4 5 1
4 5 8 1
2 6 1 1
2 7 5 0
5 8 6 1
5 9 9 0
8 10 6 1
6 11 5 1
8 12 5 0
10 13 5 1
11 14 6 1
12 15 8 0
13 16 8 1
13 17 5 0
14 18 6 0
14 19 9 0
17 20 4 0
17 21 5 0
17 22 8 0
18 23 2 0
23 24 9 0
24 25 2 0
21 26 7 0
24 27 7 0
27 28 7 1
27 29 2 1
26 30 8 0
30 31 5 0
27 32 8 ...

output:

result:

ok 1 number(s): "45838"

Test #30:

score: 0

Accepted

time: 71ms

memory: 237672kb

input:

output:

result:

ok 1 number(s): "25924"

Test #31:

score: 0

Accepted

time: 195ms

memory: 228500kb

input:

output:

result:

ok 1 number(s): "12327"

Test #32:

score: 0

Accepted

time: 64ms

memory: 176200kb

input:

output:

result:

ok 11 numbers

Test #33:

score: 0

Accepted

time: 89ms

memory: 212432kb

input:

output:

result:

ok 5 number(s): "8836 1053 4019 3 -1"

Test #34:

score: 0

Accepted

time: 172ms

memory: 224808kb

input:

output:

result:

ok 7 numbers

Test #35:

score: 0

Accepted

time: 55ms

memory: 178560kb

input:

output:

result:

ok 8 numbers

Test #36:

score: 0

Accepted

time: 94ms

memory: 196940kb

input:

6
4878 424
1 2 3 1
2 3 10 1
3 4 2 1
3 5 9 1
4 6 7 0
4 7 7 0
5 8 5 0
4 9 2 1
2 10 4 0
3 11 7 1
2 12 9 1
1 13 4 0
5 14 3 0
3 15 7 0
4 16 8 0
4 17 6 0
4 18 9 0
3 19 1 0
1 20 3 0
2 21 7 1
5 22 5 0
2 23 6 0
3 24 4 0
2 25 3 0
1 26 7 0
5 27 8 1
1 28 3 0
5 29 3 0
1 30 6 0
2 31 4 0
4 32 1 0
3 33 1 0
2 34 4 1...

output:

result:

ok 6 numbers

Test #37:

score: 0

Accepted

time: 99ms

memory: 227880kb

input:

output:

result:

ok 4 number(s): "8810 1090 672 6"

Test #38:

score: 0

Accepted

time: 98ms

memory: 224884kb

input:

output:

result:

ok 6 numbers

Test #39:

score: 0

Accepted

time: 164ms

memory: 226468kb

input:

output:

result:

ok 4 number(s): "10827 197 301 591"

Test #40:

score: 0

Accepted

time: 115ms

memory: 236848kb

input:

output:

result:

ok 5 number(s): "16879 553 185 147 9"

Test #41:

score: 0

Accepted

time: 55ms

memory: 168624kb

input:

output:

result:

ok 7 numbers

Test #42:

score: 0

Accepted

time: 64ms

memory: 168128kb

input:

output:

result:

ok 10 numbers

Test #43:

score: 0

Accepted

time: 79ms

memory: 205028kb

input:

output:

result:

ok 7 numbers

Test #44:

score: 0

Accepted

time: 52ms

memory: 125004kb

input:

output:

result:

ok 7 numbers

Test #45:

score: 0

Accepted

time: 107ms

memory: 206536kb

input:

output:

result:

ok 7 numbers

Test #46:

score: 0

Accepted

time: 134ms

memory: 202448kb

input:

output:

result:

ok 8 numbers

Test #47:

score: 0

Accepted

time: 137ms

memory: 197000kb

input:

output:

result:

ok 6 numbers

Test #48:

score: 0

Accepted

time: 64ms

memory: 155712kb

input:

output:

result:

ok 6 numbers

Test #49:

score: 0

Accepted

time: 75ms

memory: 191828kb

input:

output:

result:

ok 6 numbers

Test #50:

score: 0

Accepted

time: 90ms

memory: 218780kb

input:

output:

result:

ok 6 numbers

Test #51:

score: 0

Accepted

time: 61ms

memory: 172180kb

input:

output:

result:

ok 9 numbers