QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#319062#5313. Please Save PigelandpeterWA 17ms20552kbC++143.2kb2024-02-01 18:15:422024-02-01 18:15:43

Judging History

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

  • [2024-02-01 18:15:43]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:20552kb
  • [2024-02-01 18:15:42]
  • 提交

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>

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];

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==0&&y.second==0) return x;
	// if(x.first==0&&x.second==0) 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 %d\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){
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].to;
		if(v==ff||(!num[v])) continue;
		if(num[v]) dfs3(v,u);
		pii tmp=gg[v];
		tmp.first+=e[i].d;
		// printf("kk%d %d %d %d\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%d %d %d\n",u,gg[u].first,gg[u].second);
}
void dfs4(int u,int ff,pii val){
	dp[u]=gg[u]+val;
	// printf("%d %d %d\n",u,fz[u],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 %d\n",u,v);
		vec[u].push_back(make_pair(v,e[i].d));
	}
	pre[0]=suf[(int)vec[u].size()+1]=make_pair(0,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("%d %d\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];
		tmp.first+=vec[u][i].second;
		// printf("kk%d %d %d\n",vec[u][i].first,tmp.first,tmp.second);
		dfs4(vec[u][i].first,u,tmp);
	}
}

int main(){
	
	init();
	
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int x;
		scanf("%d",&x);
		num[x]++;
		bk[x]=1;
	}
	for(int i=1;i<n;i++){
		int u,v,d;
		scanf("%d %d %d",&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 %d\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("%d\n",res);
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 17636kb

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: 0ms
memory: 17440kb

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: 8ms
memory: 17344kb

input:

1 1
1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 17ms
memory: 20552kb

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

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: -100
Wrong Answer
time: 0ms
memory: 17448kb

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:

1728

result:

wrong answer 1st numbers differ - expected: '1798', found: '1728'