QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#629279	#7502. Painting the Roads	Flamire	AC ✓	64ms	171376kb	C++17	1.6kb	2024-10-11 10:14:19	2024-10-11 10:14:19

Judging History

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

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

测评结果：AC
用时：64ms
内存：171376kb

查看

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

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);
	dp[u][0]=0;
	for(int i=1;i<=m/2;++i)dp[u][i]=1e18;
	for(auto [v,l,c]:G[u])if(v^F)
	{
		int pt1=1,pt2=1,pt3=1;
		ndp[0]=dp[u][0]+dp[v][0];
		while(pt3<=m/2)
		{
			if(dp[u][pt1]<dp[v][pt2])ndp[pt3++]=dp[u][pt1++];
			else ndp[pt3++]=dp[v][pt2++];
		}
		for(int j=0;j<=m/2;++j)dp[u][j]=ndp[j],ndp[j]=1e18;
	}
	for(int i=1;i<=m/2;++i)dp[u][i]=min(dp[u][i],0ll);
	dp[u][0]+=1ll*abs(ned[u]-siz[u])*faL;
	for(int j=1;j<=m/2;++j)
	{
		dp[u][j]+=1ll*abs(2*j+ned[u]-siz[u])*faL-1ll*abs(2*(j-1)+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=1;j<=m/2;++j)dp[1][j]+=dp[1][j-1];
			for(int j=0;j<=m/2;++j)if(ned[1]+j*2<=m)ans=min(ans,dp[1][j]);
			printf("%lld\n",ans);
		}
	}
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 5988kb

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

memory: 3908kb

input:

output:

result:

ok 1000 numbers

Test #3:

score: 0

Accepted

time: 2ms

memory: 3968kb

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

input:

output:

result:

ok 100 numbers

Test #5:

score: 0

Accepted

time: 7ms

memory: 24500kb

input:

output:

result:

ok 10 numbers

Test #6:

score: 0

Accepted

time: 7ms

memory: 22804kb

input:

output:

result:

ok 10 numbers

Test #7:

score: 0

Accepted

time: 5ms

memory: 22740kb

input:

output:

result:

ok 10 numbers

Test #8:

score: 0

Accepted

time: 15ms

memory: 102784kb

input:

output:

-1
-1

result:

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

Test #9:

score: 0

Accepted

time: 39ms

memory: 102532kb

input:

output:

6761
8789

result:

ok 2 number(s): "6761 8789"

Test #10:

score: 0

Accepted

time: 24ms

memory: 103152kb

input:

output:

6858
-1

result:

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

Test #11:

score: 0

Accepted

time: 34ms

memory: 91352kb

input:

output:

6616
7292

result:

ok 2 number(s): "6616 7292"

Test #12:

score: 0

Accepted

time: 27ms

memory: 133040kb

input:

output:

result:

ok 1 number(s): "18174"

Test #13:

score: 0

Accepted

time: 15ms

memory: 137272kb

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

memory: 124368kb

input:

output:

result:

ok 1 number(s): "5981"

Test #15:

score: 0

Accepted

time: 23ms

memory: 139648kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0

Accepted

time: 42ms

memory: 150368kb

input:

output:

result:

ok 1 number(s): "20709"

Test #17:

score: 0

Accepted

time: 64ms

memory: 162088kb

input:

output:

result:

ok 1 number(s): "14832"

Test #18:

score: 0

Accepted

time: 35ms

memory: 153056kb

input:

output:

result:

ok 1 number(s): "12769"

Test #19:

score: 0

Accepted

time: 37ms

memory: 153180kb

input:

output:

result:

ok 1 number(s): "11987"

Test #20:

score: 0

Accepted

time: 58ms

memory: 163124kb

input:

output:

result:

ok 1 number(s): "13461"

Test #21:

score: 0

Accepted

time: 49ms

memory: 162400kb

input:

output:

result:

ok 1 number(s): "15399"

Test #22:

score: 0

Accepted

time: 54ms

memory: 169132kb

input:

output:

result:

ok 1 number(s): "13750"

Test #23:

score: 0

Accepted

time: 40ms

memory: 160220kb

input:

output:

result:

ok 1 number(s): "12984"

Test #24:

score: 0

Accepted

time: 0ms

memory: 136676kb

input:

output:

result:

ok 1 number(s): "439"

Test #25:

score: 0

Accepted

time: 61ms

memory: 169344kb

input:

output:

result:

ok 1 number(s): "15533"

Test #26:

score: 0

Accepted

time: 15ms

memory: 150740kb

input:

output:

result:

ok 1 number(s): "8937"

Test #27:

score: 0

Accepted

time: 19ms

memory: 147384kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #28:

score: 0

Accepted

time: 48ms

memory: 171376kb

input:

output:

result:

ok 1 number(s): "13800"

Test #29:

score: 0

Accepted

time: 11ms

memory: 147400kb

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

memory: 147292kb

input:

output:

result:

ok 1 number(s): "25924"

Test #31:

score: 0

Accepted

time: 47ms

memory: 164704kb

input:

output:

result:

ok 1 number(s): "12327"

Test #32:

score: 0

Accepted

time: 16ms

memory: 90708kb

input:

output:

result:

ok 11 numbers

Test #33:

score: 0

Accepted

time: 31ms

memory: 119264kb

input:

output:

result:

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

Test #34:

score: 0

Accepted

time: 45ms

memory: 150004kb

input:

output:

result:

ok 7 numbers

Test #35:

score: 0

Accepted

time: 15ms

memory: 92168kb

input:

output:

result:

ok 8 numbers

Test #36:

score: 0

Accepted

time: 7ms

memory: 145852kb

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

memory: 146716kb

input:

output:

result:

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

Test #38:

score: 0

Accepted

time: 38ms

memory: 141996kb

input:

output:

result:

ok 6 numbers

Test #39:

score: 0

Accepted

time: 40ms

memory: 141824kb

input:

output:

result:

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

Test #40:

score: 0

Accepted

time: 31ms

memory: 151728kb

input:

output:

result:

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

Test #41:

score: 0

Accepted

time: 19ms

memory: 86668kb

input:

output:

result:

ok 7 numbers

Test #42:

score: 0

Accepted

time: 12ms

memory: 86188kb

input:

output:

result:

ok 10 numbers

Test #43:

score: 0

Accepted

time: 15ms

memory: 148336kb

input:

output:

result:

ok 7 numbers

Test #44:

score: 0

Accepted

time: 7ms

memory: 65656kb

input:

output:

result:

ok 7 numbers

Test #45:

score: 0

Accepted

time: 33ms

memory: 126852kb

input:

output:

result:

ok 7 numbers

Test #46:

score: 0

Accepted

time: 28ms

memory: 127568kb

input:

output:

result:

ok 8 numbers

Test #47:

score: 0

Accepted

time: 23ms

memory: 147072kb

input:

output:

result:

ok 6 numbers

Test #48:

score: 0

Accepted

time: 16ms

memory: 80636kb

input:

output:

result:

ok 6 numbers

Test #49:

score: 0

Accepted

time: 15ms

memory: 121232kb

input:

output:

result:

ok 6 numbers

Test #50:

score: 0

Accepted

time: 20ms

memory: 125340kb

input:

output:

result:

ok 6 numbers

Test #51:

score: 0

Accepted

time: 11ms

memory: 87924kb

input:

output:

result:

ok 9 numbers