QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#319068#5313. Please Save PigelandpeterWA 412ms103608kbC++143.6kb2024-02-01 18:42:402024-02-01 18:42:40

Judging History

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

  • [2024-02-01 18:42:40]
  • 评测
  • 测评结果:WA
  • 用时:412ms
  • 内存:103608kb
  • [2024-02-01 18:42:40]
  • 提交

answer

// Problem: qoj5313 Please Save Pigeland
// Contest: Qoj
// URL: https://qoj.ac/problem/5313
// Memory Limit: 1024 MB
// Time Limit: 3000 ms

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=5e5+5;
typedef pair<int,int> pii;
int num[maxn],fz[maxn],n,m;
struct edge{
	int to,nxt,d;
}e[maxn<<1];
int head[maxn],len,res=inf,all=0;
bool bk[maxn];
pii gg[maxn],dp[maxn];
pii pre[maxn],suf[maxn];
vector<pii> vec[maxn],vc[maxn];

int gcd(int x,int y){
	if(y==0) return x;
	return gcd(y,x%y);
}

pii operator + (pii x,pii y){
	if(y.first==-1) return x;
	if(x.first==-1) return y;
	return make_pair(x.first,gcd(gcd(x.second,y.second),abs(x.first-y.first)));
}

inline void init(){
	memset(head,-1,sizeof(head));
	len=0;
}
void add(int u,int v,int d){
	e[++len].to=v;
	e[len].d=d;
	e[len].nxt=head[u];
	head[u]=len;
}

void dfs1(int u,int f){
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].to;
		if(v==f) continue;
		dfs1(v,u);
		num[u]+=num[v];
		all+=num[v]*e[i].d;
	}
}
void dfs2(int u,int f,int val){
	fz[u]=val;
	if(val==0){
		puts("0");
		exit(0);
	}
	// printf("kk%d %lld\n",u,fz[u]);
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].to;
		if(v==f) continue;
		dfs2(v,u,val-num[v]*e[i].d+(m-num[v])*e[i].d);
	}
}
void dfs3(int u,int ff){
	if(!num[u]) gg[u].first=-1;
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].to;
		if(v==ff) continue;
		dfs3(v,u);
		if(num[v]){
			pii tmp=gg[v];
			tmp.first+=e[i].d;
			// printf("kk%d %lld %lld %lld\n",u,v,tmp.first,tmp.second);
			if(gg[u].first==0&&gg[u].second==0&&(!bk[u])) gg[u]=tmp;
			else gg[u]=gg[u]+tmp;
		}
	}
	// printf("kk%lld %lld %lld\n",u,gg[u].first,gg[u].second);
}
void dfs4(int u,int ff,pii val){
	dp[u]=gg[u]+val;
	// printf("%lld %lld %lld %lld %lld\n",u,fz[u],dp[u].first,dp[u].second,gcd(dp[u].first,dp[u].second));
	// exit(0);
	res=min(res,fz[u]/gcd(dp[u].first,dp[u].second)*2);
	vec[u].clear();
	// vec.push_back(make_pair(0,0));
	for(int i=head[u],j=1;i!=-1;i=e[i].nxt,j++){
		int v=e[i].to;
		if(v==ff) continue;
		// printf("kk%d %lld\n",u,v);
		vec[u].push_back(make_pair(v,e[i].d));
	}
	pre[0]=suf[(int)vec[u].size()+1]=make_pair(-1,0);
	for(int i=0;i<(int)vec[u].size();i++){
		pii tmp=gg[vec[u][i].first];
		tmp.first+=vec[u][i].second;
		pre[i+1]=pre[i]+tmp;
	}
	for(int i=(int)vec[u].size()-1;i>=0;i--){
		pii tmp=gg[vec[u][i].first];
		tmp.first+=vec[u][i].second;
		suf[i+1]=suf[i+2]+tmp;
	}
	// printf("kk%d\n",u);
	// for(int i=0;i<(int)vec[u].size();i++) printf("%lld %lld\n",pre[i+1].first,pre[i+1].second);
	for(int i=0;i<(int)vec[u].size();i++){
		pii tmp=val+pre[i]+suf[i+2];
		if(bk[u]){
			if(tmp.first==-1) tmp.first=0;
			tmp.first+=vec[u][i].second;
			 tmp.second=gcd(tmp.second,tmp.first);
		}else{
			if(tmp.first!=-1) tmp.first+=vec[u][i].second;
		}
		// printf("kk%lld %lld %lld %lld\n",u,vec[u][i].first,tmp.first,tmp.second);
		vc[u].push_back(tmp);
	}
	for(int i=0;i<(int)vec[u].size();i++) dfs4(vec[u][i].first,u,vc[u][i]);
}

signed main(){
	
	init();
	
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=m;i++){
		int x;
		scanf("%lld",&x);
		num[x]++;
		bk[x]=1;
	}
	for(int i=1;i<n;i++){
		int u,v,d;
		scanf("%lld %lld %lld",&u,&v,&d);
		add(u,v,d);
		add(v,u,d);
	}
	
	// pii tmp=make_pair(3,6),tmp2=make_pair(6,9),tmp3=tmp+tmp2;
	
	// printf("kkk%d %lld\n",tmp3.first,tmp3.second);
	
	dfs1(1,0);
	
	// printf("kk%d\n",all);
	
	dfs2(1,0,all);
	
	dfs3(1,0);
	
	// exit(0);
	dfs4(1,0,make_pair(0,0));
	
	printf("%lld\n",res);
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 31220kb

input:

5 3
3 4 5
1 2 2
2 3 4
2 5 4
3 4 6

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 3ms
memory: 31236kb

input:

10 3
1 7 10
7 6 3
1 8 3
3 6 3
8 6 2
4 1 1
10 6 4
2 8 3
9 10 3
5 10 3

output:

24

result:

ok 1 number(s): "24"

Test #3:

score: 0
Accepted
time: 7ms
memory: 30988kb

input:

1 1
1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 25ms
memory: 37360kb

input:

100000 1
79187
72704 72659 15
32741 43496 10
21580 97447 17
55758 36700 21
32116 3643 14
60460 58764 12
75894 50624 7
58295 49393 22
43733 17210 1
58093 68769 15
1086 58916 17
25632 37710 11
49555 92976 8
32547 27060 18
84896 12811 1
3196 1242 16
18870 78236 14
2414 7945 12
48745 15399 1
17648 83791...

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 31244kb

input:

100 10
3 27 33 45 48 72 76 91 92 100
66 98 4
70 17 2
28 59 4
26 25 3
77 92 1
40 61 2
11 27 2
85 35 1
57 26 1
68 99 4
50 84 1
20 82 3
31 39 1
71 7 4
54 55 4
60 26 4
56 61 2
15 66 3
95 53 2
8 60 4
21 82 1
18 81 2
29 73 3
94 4 1
10 4 4
86 43 1
62 41 1
45 57 1
25 66 3
69 89 2
14 53 3
27 92 1
42 98 4
13 ...

output:

200

result:

ok 1 number(s): "200"

Test #6:

score: 0
Accepted
time: 4ms
memory: 31264kb

input:

100 90
75 17 78 84 52 69 54 24 74 35 58 51 72 7 21 70 93 15 60 87 13 40 23 92 99 53 27 22 91 46 56 86 61 19 44 98 50 28 14 12 55 64 30 80 95 38 18 43 31 89 20 16 8 65 63 79 59 34 97 25 2 11 67 71 29 9 37 76 77 26 39 68 32 62 90 10 85 49 42 45 96 83 94 3 6 100 81 57 88 47
67 65 1
43 78 4
98 71 3
71 2...

output:

1798

result:

ok 1 number(s): "1798"

Test #7:

score: 0
Accepted
time: 0ms
memory: 31356kb

input:

1000 10
111 240 479 530 572 583 644 652 753 869
121 923 2
886 685 4
446 284 4
352 250 1
540 485 2
72 154 4
522 693 3
664 917 4
792 941 3
132 832 4
709 186 3
509 114 2
824 978 2
216 265 2
138 570 1
498 959 4
434 222 1
803 693 1
253 677 4
172 463 3
383 978 2
718 959 3
369 421 4
568 454 4
256 938 1
6 1...

output:

226

result:

ok 1 number(s): "226"

Test #8:

score: 0
Accepted
time: 0ms
memory: 31300kb

input:

1000 957
233 514 228 739 827 85 840 175 766 807 19 276 549 611 145 511 895 121 116 525 280 431 810 629 990 509 542 324 241 801 849 506 178 176 49 528 221 742 444 513 111 505 442 794 107 392 291 674 298 803 198 927 738 590 706 804 860 512 421 618 697 516 335 420 418 288 544 694 330 776 104 510 621 47...

output:

32602

result:

ok 1 number(s): "32602"

Test #9:

score: -100
Wrong Answer
time: 412ms
memory: 103608kb

input:

500000 4
182462 188845 259396 281751
456733 79213 9204078
395954 45205 3919968
454058 310013 734433
433648 435834 3887333
448797 138275 9946222
385528 63721 3037094
44276 184047 1799127
169565 81666 3752583
459111 229807 5534913
374868 374333 8627923
476055 408523 2692999
445258 424229 3038119
92885...

output:

486956092

result:

wrong answer 1st numbers differ - expected: '193870600', found: '486956092'