QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#629354	#7502. Painting the Roads	xhgua	WA	273ms	395364kb	C++14	1.4kb	2024-10-11 10:55:14	2024-10-11 10:55:14

Judging History

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

[2024-10-11 10:55:14]
评测

测评结果：WA
用时：273ms
内存：395364kb

查看

[2024-10-11 10:55:14]
提交

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 = -2 * n; i <= 2 * n; i++) f[u][i + 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;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3824kb

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: 7808kb

input:

output:

result:

ok 1000 numbers

Test #3:

score: 0

Accepted

time: 3ms

memory: 5908kb

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

memory: 7816kb

input:

output:

result:

ok 100 numbers

Test #5:

score: 0

Accepted

time: 27ms

memory: 42844kb

input:

output:

result:

ok 10 numbers

Test #6:

score: 0

Accepted

time: 23ms

memory: 42864kb

input:

output:

result:

ok 10 numbers

Test #7:

score: 0

Accepted

time: 25ms

memory: 42972kb

input:

output:

result:

ok 10 numbers

Test #8:

score: 0

Accepted

time: 99ms

memory: 200904kb

input:

output:

-1
-1

result:

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

Test #9:

score: 0

Accepted

time: 126ms

memory: 200936kb

input:

output:

6761
8789

result:

ok 2 number(s): "6761 8789"

Test #10:

score: 0

Accepted

time: 140ms

memory: 200624kb

input:

output:

6858
-1

result:

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

Test #11:

score: 0

Accepted

time: 142ms

memory: 199364kb

input:

output:

6616
7292

result:

ok 2 number(s): "6616 7292"

Test #12:

score: 0

Accepted

time: 150ms

memory: 395288kb

input:

output:

result:

ok 1 number(s): "18174"

Test #13:

score: 0

Accepted

time: 146ms

memory: 395056kb

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

memory: 395108kb

input:

output:

result:

ok 1 number(s): "5981"

Test #15:

score: 0

Accepted

time: 136ms

memory: 395276kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0

Accepted

time: 242ms

memory: 395288kb

input:

output:

result:

ok 1 number(s): "20709"

Test #17:

score: 0

Accepted

time: 262ms

memory: 395296kb

input:

output:

result:

ok 1 number(s): "14832"

Test #18:

score: 0

Accepted

time: 268ms

memory: 395160kb

input:

output:

result:

ok 1 number(s): "12769"

Test #19:

score: 0

Accepted

time: 200ms

memory: 395364kb

input:

output:

result:

ok 1 number(s): "11987"

Test #20:

score: 0

Accepted

time: 250ms

memory: 395140kb

input:

output:

result:

ok 1 number(s): "13461"

Test #21:

score: 0

Accepted

time: 230ms

memory: 395304kb

input:

output:

result:

ok 1 number(s): "15399"

Test #22:

score: 0

Accepted

time: 250ms

memory: 395340kb

input:

output:

result:

ok 1 number(s): "13750"

Test #23:

score: 0

Accepted

time: 221ms

memory: 395320kb

input:

output:

result:

ok 1 number(s): "12984"

Test #24:

score: 0

Accepted

time: 121ms

memory: 395240kb

input:

output:

result:

ok 1 number(s): "439"

Test #25:

score: 0

Accepted

time: 246ms

memory: 395236kb

input:

output:

result:

ok 1 number(s): "15533"

Test #26:

score: 0

Accepted

time: 146ms

memory: 395064kb

input:

output:

result:

ok 1 number(s): "8937"

Test #27:

score: 0

Accepted

time: 157ms

memory: 395288kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #28:

score: 0

Accepted

time: 273ms

memory: 395200kb

input:

output:

result:

ok 1 number(s): "13800"

Test #29:

score: 0

Accepted

time: 116ms

memory: 395320kb

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

memory: 395332kb

input:

output:

result:

ok 1 number(s): "25924"

Test #31:

score: 0

Accepted

time: 218ms

memory: 395164kb

input:

output:

result:

ok 1 number(s): "12327"

Test #32:

score: 0

Accepted

time: 71ms

memory: 176024kb

input:

output:

result:

ok 11 numbers

Test #33:

score: 0

Accepted

time: 114ms

memory: 232508kb

input:

output:

result:

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

Test #34:

score: -100

Wrong Answer

time: 171ms

memory: 323032kb

input:

output:

result:

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