QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#629350	#7502. Painting the Roads	xhgua	WA	254ms	353032kb	C++14	1.4kb	2024-10-11 10:54:04	2024-10-11 10:54:05

Judging History

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

[2024-10-11 10:54:05]
评测

测评结果：WA
用时：254ms
内存：353032kb

查看

[2024-10-11 10:54:04]
提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 5e3 + 5, S = 1e4, INF = (1 << 29);

int T, n, m, p[N], siz[N], f[N][N * 4], g[N * 4];
std::vector<std::array<int, 3>> G[N];

void chmin(int &x, int y) { if (y < x) x = y; }

void dfs(int u, int fa) {
    for (int i = -n; i <= n; i++) f[u][i + p[u] + S] = INF;
    for (int i = -n; i <= 0; i++) f[u][i + p[u] + S] = 0;
    siz[u] = p[u] + 1;
    for (auto [v, w, c] : G[u]) if (v != fa) {
        dfs(v, u);
        for (int i = -siz[u] - siz[v]; i <= siz[u] + siz[v]; i++) g[i + S] = INF;
        for (int i = -siz[u]; i <= siz[u]; i++)
            for (int j = -siz[v]; j <= siz[v]; j++)
                if (c == (j & 1)) chmin(g[i + j + S], f[u][i + S] + f[v][j + S] + std::abs(j) * w);
        for (int i = -siz[u] - siz[v]; i <= siz[u] + siz[v]; i++) f[u][i + S] = g[i + S];
        siz[u] += siz[v];
    }
}

void solve() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = 0, G[i].clear();
    for (int i = 1; i < n; i++) {
        int u, v, w, c; std::cin >> u >> v >> w >> c;
        G[u].push_back({v, w, c});
        G[v].push_back({u, w, c});
    }
    for (int i = 1, x; i <= m; i++) std::cin >> x, p[x]++;
    dfs(1, 0); std::cout << (f[1][S] == INF ? -1 : f[1][S]) << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> T;
    while (T--) solve();

    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3760kb

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: 0ms

memory: 5660kb

input:

output:

result:

ok 1000 numbers

Test #3:

score: 0

Accepted

time: 3ms

memory: 5776kb

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: 2ms

memory: 7944kb

input:

output:

result:

ok 100 numbers

Test #5:

score: 0

Accepted

time: 25ms

memory: 42888kb

input:

output:

result:

ok 10 numbers

Test #6:

score: 0

Accepted

time: 19ms

memory: 42872kb

input:

output:

result:

ok 10 numbers

Test #7:

score: 0

Accepted

time: 25ms

memory: 42928kb

input:

output:

result:

ok 10 numbers

Test #8:

score: 0

Accepted

time: 80ms

memory: 199224kb

input:

output:

-1
-1

result:

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

Test #9:

score: 0

Accepted

time: 120ms

memory: 199240kb

input:

output:

6761
8789

result:

ok 2 number(s): "6761 8789"

Test #10:

score: 0

Accepted

time: 151ms

memory: 200988kb

input:

output:

6858
-1

result:

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

Test #11:

score: 0

Accepted

time: 130ms

memory: 199296kb

input:

output:

6616
7292

result:

ok 2 number(s): "6616 7292"

Test #12:

score: 0

Accepted

time: 131ms

memory: 325556kb

input:

output:

result:

ok 1 number(s): "18174"

Test #13:

score: 0

Accepted

time: 180ms

memory: 326168kb

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: 112ms

memory: 335388kb

input:

output:

result:

ok 1 number(s): "5981"

Test #15:

score: 0

Accepted

time: 141ms

memory: 336476kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0

Accepted

time: 176ms

memory: 335676kb

input:

output:

result:

ok 1 number(s): "20709"

Test #17:

score: 0

Accepted

time: 254ms

memory: 335716kb

input:

output:

result:

ok 1 number(s): "14832"

Test #18:

score: 0

Accepted

time: 217ms

memory: 340944kb

input:

output:

result:

ok 1 number(s): "12769"

Test #19:

score: 0

Accepted

time: 209ms

memory: 339996kb

input:

output:

result:

ok 1 number(s): "11987"

Test #20:

score: 0

Accepted

time: 219ms

memory: 346512kb

input:

output:

result:

ok 1 number(s): "13461"

Test #21:

score: 0

Accepted

time: 211ms

memory: 346776kb

input:

output:

result:

ok 1 number(s): "15399"

Test #22:

score: 0

Accepted

time: 247ms

memory: 347364kb

input:

output:

result:

ok 1 number(s): "13750"

Test #23:

score: 0

Accepted

time: 203ms

memory: 348328kb

input:

output:

result:

ok 1 number(s): "12984"

Test #24:

score: 0

Accepted

time: 108ms

memory: 350080kb

input:

output:

result:

ok 1 number(s): "439"

Test #25:

score: 0

Accepted

time: 235ms

memory: 350584kb

input:

output:

result:

ok 1 number(s): "15533"

Test #26:

score: 0

Accepted

time: 116ms

memory: 348208kb

input:

output:

result:

ok 1 number(s): "8937"

Test #27:

score: 0

Accepted

time: 134ms

memory: 350420kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #28:

score: 0

Accepted

time: 244ms

memory: 350080kb

input:

output:

result:

ok 1 number(s): "13800"

Test #29:

score: 0

Accepted

time: 103ms

memory: 353032kb

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: 113ms

memory: 352108kb

input:

output:

result:

ok 1 number(s): "25924"

Test #31:

score: 0

Accepted

time: 205ms

memory: 352920kb

input:

output:

result:

ok 1 number(s): "12327"

Test #32:

score: 0

Accepted

time: 62ms

memory: 175992kb

input:

output:

result:

ok 11 numbers

Test #33:

score: 0

Accepted

time: 112ms

memory: 231848kb

input:

output:

result:

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

Test #34:

score: -100

Wrong Answer

time: 172ms

memory: 309420kb

input:

output:

result:

wrong answer 3rd numbers differ - expected: '11', found: '1295'