QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217919#5313. Please Save PigelandshiroiCompile Error//C++142.1kb2023-10-17 16:03:152023-10-17 16:03:16

Judging History

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

  • [2023-10-17 16:03:16]
  • 评测
  • [2023-10-17 16:03:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
	int x=0,f=1,c=getchar();
	while(c<48) c=='-'&&(f=-1),c=getchar();
	while(c>47) x=x*10+c-'0',c=getchar();
	return x*f;
}

typedef long long ll;
const ll MAXN = 2000005;
struct Edge {ll to,val;};
std::vector<Edge> G[MAXN];
ll s[MAXN<<2],dis[MAXN],st[MAXN],size[MAXN];
ll dfnl[MAXN],ispt[MAXN],dfnr[MAXN];
ll n,m,top,dft=1;
ll sumdis,ans=2e18;

inline void addedge(ll u,ll v,ll w)
{
	G[u].push_back(Edge{v,w});
	G[v].push_back(Edge{u,w});
}

inline int gcd(int a,int b)
{return b ? gcd(b,a%b) : abs(a);}

void pushup(int rt)
{
	s[rt]=gcd(s[rt<<1],s[rt<<1|1]);
}

void build(int l=1,int r=m,int rt=1)
{
	if(l==r) return void(s[rt]=dis[st[l]]-dis[st[l-1]]);
	int mid=(l+r)>>1;
	build(l,mid,rt<<1); build(mid+1,r,rt<<1|1);
	pushup(rt);
}

void update(int p,int k,int l=1,int r=m,int x=1)
{
	if(l==r) return s[x]+=k,void();
	int mid=(l+r)>>1;
	if(p<=mid) update(p,k,l,mid,x<<1);
	if(p>mid)  update(p,k,mid+1,r,x<<1|1);
	pushup(x);
}

ll query() {return abs(s[1]);}
ll sum,ans=1e18;

void dfs(int u,int fa=0)
{
	if(ispt[u])
	{
		st[dfnl[u]=++dfnl[0]]=u;
		sum+=dis[u]; size[u]=1;
	}
	else
	{
		dfnl[u]=dfnl[0]+1;
	}
	for(Edge e : G[u])
	{
		if(e.to==fa) continue;
		dis[e.to]=dis[u]+e.val;
		dfs(e.to,u); size[u]+=size[e.to];
	}
	dfnr[u]=dfnl[0];
}

void modify(int l,int r,int x)
{
	if(l>r)return;
	update(l,x); if(r<m)update(r+1,-x);
}
void solve(int u,int fa=0)
{
	if(query()) ans=min(ans,sum/query());
	for(Edge e : G[u])
	{
		if(e.to==fa) continue;
		sum+=1ll*(m-size[e.to]*2)*e.val;
		modify(1,dfnl[e.to]-1,e.val);
		modify(dfnl[e.to],dfnr[e.to],-e.val);
		modify(dfnr[e.to]+1,m,e.val);
		solve(e.to,u);
		sum-=1ll*(m-size[e.to]*2)*e.val;
		modify(1,dfnl[e.to]-1,-e.val);
		modify(dfnl[e.to],dfnr[e.to],e.val);
		modify(dfnr[e.to]+1,m,-e.val);
	}
}

int main()
{
	n=read(); m=read();
	if(m==1) return puts("0"),0;
	for(int i=1,x; i<=m; i++) ispt[read()]=1;
	for(int i=1; i<n; ++i)
	{
		int u=read(),v=read(),w=read();
		addedge(u,v,w);
	}
	dfs(1); build(); solve(1);
	printf("%lld\n", ans*2);
	return 0;
}

Details

answer.code:53:8: error: redefinition of ‘ll ans’
   53 | ll sum,ans=1e18;
      |        ^~~
answer.code:19:11: note: ‘ll ans’ previously defined here
   19 | ll sumdis,ans=2e18;
      |           ^~~