QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#629265#7502. Painting the RoadsFlamireTL 640ms102748kbC++171.6kb2024-10-11 10:05:212024-10-11 10:05:22

Judging History

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

  • [2024-10-11 10:05:22]
  • 评测
  • 测评结果：TL
  • 用时：640ms
  • 内存：102748kb
查看
  • [2024-10-11 10:05:21]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[5011][5011],ndp[5011];
struct edge{int v,l,c;};
int n,m,t,siz[5011],col[5011],ned[5011];
vector<edge> G[5011];
void dfs(int u,int F,int faL,int faC)
{
	col[u]=faC;ned[u]=0;int tt=siz[u];
	for(auto [v,l,c]:G[u])if(v^F)
	{
		dfs(v,u,l,c);
		col[u]^=c;ned[u]+=ned[v];siz[u]+=siz[v];
	}
	if(u!=1)ned[u]+=col[u]^(tt&1);
	// printf("===========================start proc u:%d faL:%d faC:%d\n",u,faL,faC);
	// printf("siz[%d]:%d ned[%d]:%d %d^%d\n",u,siz[u],u,ned[u],col[u],tt&1);
	dp[u][0]=0;
	for(auto [v,l,c]:G[u])if(v^F)
	{
		for(int i=0;i<=m/2;++i)
		{
			for(int j=0;j+i<=m/2;++j)
			{
				ndp[i+j]=min(ndp[i+j],dp[u][i]+dp[v][j]);
			}
		}
		for(int j=0;j<=m/2;++j)dp[u][j]=ndp[j],ndp[j]=1e18;
	}
	for(int i=0;i<=m/2;++i)
	{
		for(int j=0;j+i<=m/2;++j)ndp[i+j]=min(ndp[i+j],dp[u][i]);
	}
	for(int j=0;j<=m/2;++j)dp[u][j]=ndp[j],ndp[j]=1e18;
	for(int j=0;j<=m/2;++j)dp[u][j]+=1ll*abs(2*j+ned[u]-siz[u])*faL;
}
int main()
{
	scanf("%d",&t);while(t--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)G[i].clear(),siz[i]=0;
		for(int i=1;i<=n;++i)for(int j=0;j<=m/2;++j)dp[i][j]=1e18;
		for(int j=0;j<=m/2;++j)ndp[j]=1e18;
		for(int i=1;i<n;++i)
		{
			int u,v,l,c;
			scanf("%d%d%d%d",&u,&v,&l,&c);
			G[u].push_back({v,l,c});
			G[v].push_back({u,l,c});
		}
		for(int i=1;i<=m;++i)
		{
			int x;scanf("%d",&x);
			++siz[x];
		}
		dfs(1,0,0,0);
		if(ned[1]>m)printf("-1\n");
		else
		{
			ll ans=1e18;
			for(int j=0;j<=m/2;++j)if(ned[1]+j*2<=m)ans=min(ans,dp[1][j]);
			printf("%lld\n",ans);
		}
	}
	fclose(stdin);fclose(stdout);return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4076kb

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

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

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: 3ms
memory: 6056kb

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: 175ms
memory: 24612kb

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: 197ms
memory: 24596kb

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: 185ms
memory: 22768kb

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: 640ms
memory: 102748kb

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: -100
Time Limit Exceeded

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:

result:
English 繁體中文 简体中文

Server Time: 2024-12-03 04:30:56 | OpenSource Project