QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#319060#5313. Please Save PigelandpeterRE 3ms29916kbC++143.2kb2024-02-01 18:13:412024-02-01 18:13:41

Judging History

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

  • [2024-02-01 18:13:41]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:29916kb
  • [2024-02-01 18:13:41]
  • 提交

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;
	// 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;
	res=min(res,fz[u]/gcd(dp[u].first,dp[u].second)*2);
	// printf("%d %d %d\n",u,fz[u],gcd(dp[u].first,dp[u].second));
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 28856kb

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

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: -100
Runtime Error

input:

1 1
1

output:


result: