QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217923#5313. Please Save PigelandshiroiCompile Error//C++142.1kb2023-10-17 16:05:012023-10-17 16:05:01

Judging History

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

  • [2023-10-17 16:05:01]
  • 评测
  • [2023-10-17 16:05:01]
  • 提交

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 x,int y,int l=1,int r=m,int rt=1)
{
	if(l==r)return s[rt]+=y,void(); int mid=(l+r)>>1;
	x<=mid?update(x,y,l,mid,rt<<1):update(x,y,mid+1,r,rt<<1|1); pushup(rt);
}
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++)scanf("%d",&x),ispt[x]=1;
	for(int i=1,u,v,w; i<n; i++)scanf("%d%d%d",&u,&v,&w),addedge(u,v,w);
	dfs(1); build(); solve(1);
	cout<<ans*2;
	return 0;
}

Details

answer.code:45:8: error: redefinition of ‘ll ans’
   45 | ll sum,ans=1e18;
      |        ^~~
answer.code:19:11: note: ‘ll ans’ previously defined here
   19 | ll sumdis,ans=2e18;
      |           ^~~
answer.code: In function ‘int main()’:
answer.code:93:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   93 |         for(int i=1,x; i<=m; i++)scanf("%d",&x),ispt[x]=1;
      |                                  ~~~~~^~~~~~~~~
answer.code:94:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   94 |         for(int i=1,u,v,w; i<n; i++)scanf("%d%d%d",&u,&v,&w),addedge(u,v,w);
      |                                     ~~~~~^~~~~~~~~~~~~~~~~~~