QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#629290	#7502. Painting the Roads	lsj2009	RE	369ms	449672kb	C++20	2.3kb	2024-10-11 10:19:57	2024-10-11 10:19:58

Judging History

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

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

测评结果：RE
用时：369ms
内存：449672kb

查看

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

answer

#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
//#define int long long
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
//	system("fc .out .ans");
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
bool M1;
const int N=5e3+5;
int head[N],len;
struct node {
	int to,c,w,nxt;
}; node edge[N<<1];
void add_edge(int u,int v,int c,int w) {
	edge[++len]={v,c,w,head[u]}; head[u]=len;
}
int f[N][N*5],tmp[N*5],siz[N],n,m;
int cnt[N];
void dfs(int u,int fa) {
	siz[u]=cnt[u]+max(cnt[u],1);
	rep(i,-siz[u],0)
		f[u][2*n+i+cnt[u]]=0;
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].to,c=edge[i].c,w=edge[i].w;
		if(v!=fa) {
			dfs(v,u);
			rep(i,-siz[u],+siz[u]) {
				tmp[2*n+i]=f[u][2*n+i];
				f[u][2*n+i]=INF;
			}
			rep(i,-siz[u],+siz[u]) {
				rep(j,-siz[v],+siz[v]) {
					if((abs(j)&1)==c)
						chkmin(f[u][2*n+i+j],tmp[2*n+i]+f[v][2*n+j]+abs(j)*w);
				}
			}
			siz[u]+=siz[v];
		}
	}
}
/*
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
*/
void solve() {
	len=0;
	rep(i,1,n)
		head[i]=cnt[i]=0;
	rep(i,1,n) {
		rep(j,0,n+n+n+n)
			f[i][j]=INF;
	}
	scanf("%d%d",&n,&m);
	rep(i,1,n) {
		rep(j,0,n+n+n+n)
			f[i][j]=INF;
	}
	rep(i,2,n) {
		int u,v,w,c;
		scanf("%d%d%d%d",&u,&v,&w,&c);
		add_edge(u,v,c,w);
		add_edge(v,u,c,w);
	}
	while(m--) {
		int x;
		scanf("%d",&x);
		++cnt[x];
	}
	dfs(1,0);
	printf("%d\n",f[1][2*n]>=INF? -1:f[1][2*n]);
}
bool M2;
signed main() {
	//file_IO();
	int testcase=1;
	scanf("%d",&testcase);
	while(testcase--)
		solve();
	fprintf(stderr,"used time = %ldms\n",1000*clock()/CLOCKS_PER_SEC);
	fprintf(stderr,"used memory = %lldMB\n",(&M2-&M1)/1024/1024);
	return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 5956kb

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

input:

output:

result:

ok 1000 numbers

Test #3:

score: 0

Accepted

time: 3ms

memory: 6044kb

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

memory: 10096kb

input:

output:

result:

ok 100 numbers

Test #5:

score: 0

Accepted

time: 39ms

memory: 53284kb

input:

output:

result:

ok 10 numbers

Test #6:

score: 0

Accepted

time: 40ms

memory: 53172kb

input:

output:

result:

ok 10 numbers

Test #7:

score: 0

Accepted

time: 40ms

memory: 53408kb

input:

output:

result:

ok 10 numbers

Test #8:

score: 0

Accepted

time: 91ms

memory: 224152kb

input:

output:

-1
-1

result:

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

Test #9:

score: 0

Accepted

time: 177ms

memory: 225296kb

input:

output:

6761
8789

result:

ok 2 number(s): "6761 8789"

Test #10:

score: 0

Accepted

time: 226ms

memory: 233264kb

input:

output:

6858
-1

result:

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

Test #11:

score: 0

Accepted

time: 211ms

memory: 233300kb

input:

output:

6616
7292

result:

ok 2 number(s): "6616 7292"

Test #12:

score: 0

Accepted

time: 168ms

memory: 448056kb

input:

output:

result:

ok 1 number(s): "18174"

Test #13:

score: 0

Accepted

time: 137ms

memory: 449332kb

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

memory: 449456kb

input:

output:

result:

ok 1 number(s): "5981"

Test #15:

score: 0

Accepted

time: 168ms

memory: 449500kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0

Accepted

time: 250ms

memory: 449476kb

input:

output:

result:

ok 1 number(s): "20709"

Test #17:

score: 0

Accepted

time: 369ms

memory: 449444kb

input:

output:

result:

ok 1 number(s): "14832"

Test #18:

score: 0

Accepted

time: 224ms

memory: 449276kb

input:

output:

result:

ok 1 number(s): "12769"

Test #19:

score: 0

Accepted

time: 187ms

memory: 449624kb

input:

output:

result:

ok 1 number(s): "11987"

Test #20:

score: 0

Accepted

time: 269ms

memory: 449252kb

input:

output:

result:

ok 1 number(s): "13461"

Test #21:

score: 0

Accepted

time: 291ms

memory: 449384kb

input:

output:

result:

ok 1 number(s): "15399"

Test #22:

score: 0

Accepted

time: 324ms

memory: 449672kb

input:

output:

result:

ok 1 number(s): "13750"

Test #23:

score: 0

Accepted

time: 243ms

memory: 449236kb

input:

output:

result:

ok 1 number(s): "12984"

Test #24:

score: 0

Accepted

time: 104ms

memory: 449260kb

input:

output:

result:

ok 1 number(s): "439"

Test #25:

score: 0

Accepted

time: 350ms

memory: 449584kb

input:

output:

result:

ok 1 number(s): "15533"

Test #26:

score: 0

Accepted

time: 127ms

memory: 449216kb

input:

output:

result:

ok 1 number(s): "8937"

Test #27:

score: 0

Accepted

time: 157ms

memory: 449296kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #28:

score: 0

Accepted

time: 301ms

memory: 449240kb

input:

output:

result:

ok 1 number(s): "13800"

Test #29:

score: 0

Accepted

time: 108ms

memory: 449456kb

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

memory: 449336kb

input:

output:

result:

ok 1 number(s): "25924"

Test #31:

score: 0

Accepted

time: 235ms

memory: 449540kb

input:

output:

result:

ok 1 number(s): "12327"

Test #32:

score: 0

Accepted

time: 119ms

memory: 219424kb

input:

output:

result:

ok 11 numbers

Test #33:

score: 0

Accepted

time: 205ms

memory: 254636kb

input:

output:

result:

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

Test #34:

score: 0

Accepted

time: 291ms

memory: 344828kb

input:

output:

result:

ok 7 numbers

Test #35:

score: 0

Accepted

time: 124ms

memory: 219892kb

input:

output:

result:

ok 8 numbers

Test #36:

score: 0

Accepted

time: 179ms

memory: 434544kb

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

memory: 375512kb

input:

output:

result:

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

Test #38:

score: 0

Accepted

time: 213ms

memory: 305096kb

input:

output:

result:

ok 6 numbers

Test #39:

score: 0

Accepted

time: 278ms

memory: 340396kb

input:

output:

result:

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

Test #40:

score: 0

Accepted

time: 268ms

memory: 410508kb

input:

output:

result:

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

Test #41:

score: 0

Accepted

time: 144ms

memory: 211432kb

input:

output:

result:

ok 7 numbers

Test #42:

score: 0

Accepted

time: 112ms

memory: 209120kb

input:

output:

result:

ok 10 numbers

Test #43:

score: 0

Accepted

time: 164ms

memory: 342144kb

input:

output:

result:

ok 7 numbers

Test #44:

score: 0

Accepted

time: 129ms

memory: 155592kb

input:

output:

result:

ok 7 numbers

Test #45:

score: 0

Accepted

time: 229ms

memory: 284928kb

input:

output:

result:

ok 7 numbers

Test #46:

score: 0

Accepted

time: 192ms

memory: 285944kb

input:

output:

result:

ok 8 numbers

Test #47:

score: 0

Accepted

time: 234ms

memory: 384524kb

input:

output:

result:

ok 6 numbers

Test #48:

score: 0

Accepted

time: 133ms

memory: 193120kb

input:

output:

result:

ok 6 numbers

Test #49:

score: -100

Runtime Error

input: