QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#319069#5313. Please Save PigelandpeterWA 3ms31240kbC++143.6kb2024-02-01 18:45:032024-02-01 18:45:04

Judging History

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

  • [2024-02-01 18:45:04]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:31240kb
  • [2024-02-01 18:45:03]
  • 提交

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(-1,0));
	
	printf("%lld\n",res);
	
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 31240kb

input:

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

output:

2

result:

wrong answer 1st numbers differ - expected: '8', found: '2'