QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#629473	#7502. Painting the Roads	OccDreamer	AC ✓	79ms	199760kb	C++14	2.7kb	2024-10-11 12:14:12	2024-10-11 12:14:12

Judging History

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

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

测评结果：AC
用时：79ms
内存：199760kb

查看

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

answer

//Mashiro
#include<bits/stdc++.h>

#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define OccDreamer
//#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(int x){write(x), putchar(32);}
	inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;

const int MAXN = 5005;
const int mod = 998244353;

int n, m, f[MAXN][MAXN<<1], siz[MAXN], g[MAXN<<1], sz[MAXN];
int head[MAXN], ne[MAXN<<1], to[MAXN<<1], weight[MAXN<<1], ban[MAXN<<1], cnt;

inline void add(int x, int y, int w, int c){++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;weight[cnt]=w; ban[cnt]=c;}

inline void dfs(int x, int fa){
	//cerr << "dfs:" << x << ' ' << fa << endl;
	sz[x]=1; f[x][sz[x]-1]=0; int ouf, co, news;
	for(int i=0;i<=siz[x];++i) f[x][i+sz[x]]=0;
	// val range : [0,siz[x]+sz[x]]
	// f[i][j] 表示在 i 这一个点，j>sz[x] 表示向上出去了 j-sz[x] 条，j<=sz[x] 表示上面进来了 sz[x]-j 条 
	for(int i=head[x];i;i=ne[i]){
		if(to[i]==fa) continue; dfs(to[i],x);	
		for(int j=0;j<=sz[x]+siz[x];++j) g[j]=f[x][j], f[x][j]=1e9;
		news=sz[x]+sz[to[i]];
		for(int j=0;j<=sz[x]+siz[x];++j){
			for(int k=0;k<=sz[to[i]]+siz[to[i]];++k){
				if(ban[i]==((k-sz[to[i]])&1)) continue;
				ouf=k-sz[to[i]];
				co=abs(ouf)*weight[i];
				ouf+=j-sz[x];
				f[x][news+ouf]=min(g[j]+f[to[i]][k]+co,f[x][news+ouf]);
			}
		}
		sz[x]+=sz[to[i]]; siz[x]+=siz[to[i]];
	}
	return ;
}

inline void solve(){
	n=read(), m=read(); cnt=0;
	for(int i=1;i<=n;++i) head[i]=0;
	for(int i=1;i<=n;++i) memset(f[i],127/3,sizeof f[i]);
	for(int i=1;i<=n;++i) siz[i]=0;
	for(int i=2;i<=n;++i){
		int x, y, w, c;
		x=read(), y=read(), w=read(), c=read();
		add(x,y,w,!c), add(y,x,w,!c);
	}
	int x;
	for(int i=1;i<=m;++i) x=read(), siz[x]++;
	dfs(1,0); 
	int ans=f[1][n];
	if(ans>n*m*10) eprint(-1);
	else eprint(ans);
}

signed main(){
	int t=read();
	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: 4056kb

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

memory: 3936kb

input:

output:

result:

ok 1000 numbers

Test #3:

score: 0

Accepted

time: 4ms

memory: 5716kb

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

memory: 5792kb

input:

output:

result:

ok 100 numbers

Test #5:

score: 0

Accepted

time: 13ms

memory: 23484kb

input:

output:

result:

ok 10 numbers

Test #6:

score: 0

Accepted

time: 12ms

memory: 24156kb

input:

output:

result:

ok 10 numbers

Test #7:

score: 0

Accepted

time: 14ms

memory: 25064kb

input:

output:

result:

ok 10 numbers

Test #8:

score: 0

Accepted

time: 29ms

memory: 103592kb

input:

output:

-1
-1

result:

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

Test #9:

score: 0

Accepted

time: 38ms

memory: 103560kb

input:

output:

6761
8789

result:

ok 2 number(s): "6761 8789"

Test #10:

score: 0

Accepted

time: 41ms

memory: 101960kb

input:

output:

6858
-1

result:

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

Test #11:

score: 0

Accepted

time: 44ms

memory: 102164kb

input:

output:

6616
7292

result:

ok 2 number(s): "6616 7292"

Test #12:

score: 0

Accepted

time: 36ms

memory: 199616kb

input:

output:

result:

ok 1 number(s): "18174"

Test #13:

score: 0

Accepted

time: 32ms

memory: 199444kb

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

memory: 199320kb

input:

output:

result:

ok 1 number(s): "5981"

Test #15:

score: 0

Accepted

time: 39ms

memory: 199600kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0

Accepted

time: 61ms

memory: 199576kb

input:

output:

result:

ok 1 number(s): "20709"

Test #17:

score: 0

Accepted

time: 79ms

memory: 199760kb

input:

output:

result:

ok 1 number(s): "14832"

Test #18:

score: 0

Accepted

time: 47ms

memory: 199372kb

input:

output:

result:

ok 1 number(s): "12769"

Test #19:

score: 0

Accepted

time: 62ms

memory: 199360kb

input:

output:

result:

ok 1 number(s): "11987"

Test #20:

score: 0

Accepted

time: 55ms

memory: 199548kb

input:

output:

result:

ok 1 number(s): "13461"

Test #21:

score: 0

Accepted

time: 57ms

memory: 199508kb

input:

output:

result:

ok 1 number(s): "15399"

Test #22:

score: 0

Accepted

time: 72ms

memory: 199416kb

input:

output:

result:

ok 1 number(s): "13750"

Test #23:

score: 0

Accepted

time: 44ms

memory: 199460kb

input:

output:

result:

ok 1 number(s): "12984"

Test #24:

score: 0

Accepted

time: 23ms

memory: 199300kb

input:

output:

result:

ok 1 number(s): "439"

Test #25:

score: 0

Accepted

time: 68ms

memory: 199652kb

input:

output:

result:

ok 1 number(s): "15533"

Test #26:

score: 0

Accepted

time: 31ms

memory: 199368kb

input:

output:

result:

ok 1 number(s): "8937"

Test #27:

score: 0

Accepted

time: 40ms

memory: 199568kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #28:

score: 0

Accepted

time: 64ms

memory: 199380kb

input:

output:

result:

ok 1 number(s): "13800"

Test #29:

score: 0

Accepted

time: 26ms

memory: 199520kb

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

memory: 199636kb

input:

output:

result:

ok 1 number(s): "25924"

Test #31:

score: 0

Accepted

time: 52ms

memory: 199452kb

input:

output:

result:

ok 1 number(s): "12327"

Test #32:

score: 0

Accepted

time: 29ms

memory: 89968kb

input:

output:

result:

ok 11 numbers

Test #33:

score: 0

Accepted

time: 35ms

memory: 118616kb

input:

output:

result:

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

Test #34:

score: 0

Accepted

time: 68ms

memory: 163252kb

input:

output:

result:

ok 7 numbers

Test #35:

score: 0

Accepted

time: 27ms

memory: 90996kb

input:

output:

result:

ok 8 numbers

Test #36:

score: 0

Accepted

time: 27ms

memory: 195704kb

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

input:

output:

result:

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

Test #38:

score: 0

Accepted

time: 39ms

memory: 145456kb

input:

output:

result:

ok 6 numbers

Test #39:

score: 0

Accepted

time: 44ms

memory: 162364kb

input:

output:

result:

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

Test #40:

score: 0

Accepted

time: 49ms

memory: 188916kb

input:

output:

result:

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

Test #41:

score: 0

Accepted

time: 31ms

memory: 87864kb

input:

output:

result:

ok 7 numbers

Test #42:

score: 0

Accepted

time: 26ms

memory: 85192kb

input:

output:

result:

ok 10 numbers

Test #43:

score: 0

Accepted

time: 28ms

memory: 162908kb

input:

output:

result:

ok 7 numbers

Test #44:

score: 0

Accepted

time: 24ms

memory: 65608kb

input:

output:

result:

ok 7 numbers

Test #45:

score: 0

Accepted

time: 34ms

memory: 138932kb

input:

output:

result:

ok 7 numbers

Test #46:

score: 0

Accepted

time: 48ms

memory: 136416kb

input:

output:

result:

ok 8 numbers

Test #47:

score: 0

Accepted

time: 39ms

memory: 177500kb

input:

output:

result:

ok 6 numbers

Test #48:

score: 0

Accepted

time: 28ms

memory: 81508kb

input:

output:

result:

ok 6 numbers

Test #49:

score: 0

Accepted

time: 45ms

memory: 122824kb

input:

output:

result:

ok 6 numbers

Test #50:

score: 0

Accepted

time: 30ms

memory: 126656kb

input:

output:

result:

ok 6 numbers

Test #51:

score: 0

Accepted

time: 23ms

memory: 87960kb

input:

output:

result:

ok 9 numbers