QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#630083	#7502. Painting the Roads	zhouyuhang	AC ✓	61ms	200332kb	C++14	2.1kb	2024-10-11 16:25:01	2024-10-11 16:25:01

Judging History

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

[2024-10-11 16:25:01]
评测

测评结果：AC
用时：61ms
内存：200332kb

查看

[2024-10-11 16:25:01]
提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5000 + 10, inf = 0x3f3f3f3f;

int t;
int n, m;
vector<array<int, 3>> e[N];
int cnt[N];

int col[N], sum[N], c1[N];
void dfs1(int u, int p) {
	for (auto &[v, l, c]: e[u]) if (v != p) col[u] ^= c, col[v] ^= c, dfs1(v, u);
}

int siz[N], f[N][N << 1];
void dfs2(int u, int p) {
	siz[u] = cnt[u] + col[u], c1[u] = col[u];
	memset(f[u], 0x3f, sizeof f[u]); f[u][cnt[u]] = 0;
	for (auto &[v, l, c]: e[u]) if (v != p) {
		dfs2(v, u);
		for (int i = siz[v]; ~i; --i) f[v][i] += abs(i - c1[v]) * l;
		for (int i = siz[u] + siz[v]; ~i; --i) {
			f[u][i] = min(f[u][i] + f[v][0], inf);
			for (int j = max(i - siz[u], 1); j <= min(siz[v], i); ++j) {
			//	cerr << u << ' ' << i - j << ' ' << f[u][i - j] << endl;
			//	cerr << v << ' ' << j << ' ' << f[v][j] << endl;
				f[u][i] = min(f[u][i], f[u][i - j] + f[v][j]);
			}
		}	
		siz[u] += siz[v], c1[u] += c1[v];
	}

	for (int i = siz[u] - 2; i >= c1[u]; --i) f[u][i] = min(f[u][i], f[u][i + 2]);
	
//	cerr << u << ": " << endl;
//	for (int i = 0; i <= siz[u]; ++i) cerr << f[u][i] << " \n"[i == siz[u]];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 1; i <= n; ++i) e[i].clear(), cnt[i] = col[i] = 0;
		for (int i = 1; i < n; ++i) {
			int u, v, l, c;
			cin >> u >> v >> l >> c;
			e[u].push_back({v, l, c});
			e[v].push_back({u, l, c});
		}
		for (int i = 1, x; i <= m; ++i) cin >> x, cnt[x]++;
		
		dfs1(1, 1); int c = 0; col[1] = 0;
		for (int i = 2; i <= n; ++i) col[i] ^= (cnt[i] & 1), c += col[i];
		
		if (c > m) {
			cout << -1 << endl;
			continue;
		}
		
		dfs2(1, 1);
		int ans = inf;
		for (int i = c1[1]; i <= siz[1]; ++i) ans = min(ans, f[1][i]);
		cout << ans << endl;
	}
	
	return 0;
}

/*
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
*/

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 6276kb

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

memory: 6044kb

input:

output:

result:

ok 1000 numbers

Test #3:

score: 0

Accepted

time: 4ms

memory: 6544kb

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

memory: 7688kb

input:

output:

result:

ok 100 numbers

Test #5:

score: 0

Accepted

time: 19ms

memory: 23628kb

input:

output:

result:

ok 10 numbers

Test #6:

score: 0

Accepted

time: 11ms

memory: 24724kb

input:

output:

result:

ok 10 numbers

Test #7:

score: 0

Accepted

time: 11ms

memory: 24084kb

input:

output:

result:

ok 10 numbers

Test #8:

score: 0

Accepted

time: 2ms

memory: 5996kb

input:

output:

-1
-1

result:

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

Test #9:

score: 0

Accepted

time: 41ms

memory: 103888kb

input:

output:

6761
8789

result:

ok 2 number(s): "6761 8789"

Test #10:

score: 0

Accepted

time: 42ms

memory: 101944kb

input:

output:

6858
-1

result:

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

Test #11:

score: 0

Accepted

time: 48ms

memory: 102768kb

input:

output:

6616
7292

result:

ok 2 number(s): "6616 7292"

Test #12:

score: 0

Accepted

time: 16ms

memory: 199972kb

input:

output:

result:

ok 1 number(s): "18174"

Test #13:

score: 0

Accepted

time: 19ms

memory: 199856kb

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

memory: 199820kb

input:

output:

result:

ok 1 number(s): "5981"

Test #15:

score: 0

Accepted

time: 0ms

memory: 4052kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0

Accepted

time: 52ms

memory: 199968kb

input:

output:

result:

ok 1 number(s): "20709"

Test #17:

score: 0

Accepted

time: 56ms

memory: 199916kb

input:

output:

result:

ok 1 number(s): "14832"

Test #18:

score: 0

Accepted

time: 39ms

memory: 199724kb

input:

output:

result:

ok 1 number(s): "12769"

Test #19:

score: 0

Accepted

time: 31ms

memory: 200104kb

input:

output:

result:

ok 1 number(s): "11987"

Test #20:

score: 0

Accepted

time: 61ms

memory: 199776kb

input:

output:

result:

ok 1 number(s): "13461"

Test #21:

score: 0

Accepted

time: 48ms

memory: 199968kb

input:

output:

result:

ok 1 number(s): "15399"

Test #22:

score: 0

Accepted

time: 60ms

memory: 199708kb

input:

output:

result:

ok 1 number(s): "13750"

Test #23:

score: 0

Accepted

time: 48ms

memory: 199772kb

input:

output:

result:

ok 1 number(s): "12984"

Test #24:

score: 0

Accepted

time: 24ms

memory: 199808kb

input:

output:

result:

ok 1 number(s): "439"

Test #25:

score: 0

Accepted

time: 58ms

memory: 199908kb

input:

output:

result:

ok 1 number(s): "15533"

Test #26:

score: 0

Accepted

time: 12ms

memory: 199744kb

input:

output:

result:

ok 1 number(s): "8937"

Test #27:

score: 0

Accepted

time: 2ms

memory: 4048kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #28:

score: 0

Accepted

time: 52ms

memory: 199852kb

input:

output:

result:

ok 1 number(s): "13800"

Test #29:

score: 0

Accepted

time: 8ms

memory: 199848kb

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

memory: 200332kb

input:

output:

result:

ok 1 number(s): "25924"

Test #31:

score: 0

Accepted

time: 43ms

memory: 199800kb

input:

output:

result:

ok 1 number(s): "12327"

Test #32:

score: 0

Accepted

time: 28ms

memory: 90380kb

input:

output:

result:

ok 11 numbers

Test #33:

score: 0

Accepted

time: 35ms

memory: 118612kb

input:

output:

result:

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

Test #34:

score: 0

Accepted

time: 36ms

memory: 163088kb

input:

output:

result:

ok 7 numbers

Test #35:

score: 0

Accepted

time: 23ms

memory: 91396kb

input:

output:

result:

ok 8 numbers

Test #36:

score: 0

Accepted

time: 27ms

memory: 195060kb

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

memory: 176848kb

input:

output:

result:

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

Test #38:

score: 0

Accepted

time: 36ms

memory: 147448kb

input:

output:

result:

ok 6 numbers

Test #39:

score: 0

Accepted

time: 51ms

memory: 161208kb

input:

output:

result:

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

Test #40:

score: 0

Accepted

time: 40ms

memory: 187348kb

input:

output:

result:

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

Test #41:

score: 0

Accepted

time: 27ms

memory: 87960kb

input:

output:

result:

ok 7 numbers

Test #42:

score: 0

Accepted

time: 25ms

memory: 87220kb

input:

output:

result:

ok 10 numbers

Test #43:

score: 0

Accepted

time: 7ms

memory: 163600kb

input:

output:

result:

ok 7 numbers

Test #44:

score: 0

Accepted

time: 21ms

memory: 44704kb

input:

output:

result:

ok 7 numbers

Test #45:

score: 0

Accepted

time: 36ms

memory: 139548kb

input:

output:

result:

ok 7 numbers

Test #46:

score: 0

Accepted

time: 42ms

memory: 137316kb

input:

output:

result:

ok 8 numbers

Test #47:

score: 0

Accepted

time: 20ms

memory: 177480kb

input:

output:

result:

ok 6 numbers

Test #48:

score: 0

Accepted

time: 24ms

memory: 81080kb

input:

output:

result:

ok 6 numbers

Test #49:

score: 0

Accepted

time: 18ms

memory: 58804kb

input:

output:

result:

ok 6 numbers

Test #50:

score: 0

Accepted

time: 28ms

memory: 125732kb

input:

output:

result:

ok 6 numbers

Test #51:

score: 0

Accepted

time: 24ms

memory: 87700kb

input:

output:

result:

ok 9 numbers