求助,洛谷AC但本地大样例4 RE
查看原帖
求助,洛谷AC但本地大样例4 RE
482856
TigerNick楼主2024/6/8 12:12

用的freopen,这是本地的问题吗

Process exited after 1.591 seconds with return value 3221225725 请按任意键继续. . .

#include <bits/stdc++.h>
#define MAXN 100010
#define i128 __int128
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int vis[MAXN],fa[MAXN],date[MAXN];
int n,u,v;
vector<int> p[MAXN];
int read()
{
	char ch=getchar();
	int f=1; int s=0;
	while(ch=='-')
	{
		f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		s=s*10+ch-'0';
		ch=getchar();
	}
	return f*s;
}
struct node
{
	int a,b,c;
	int id;
	int x,date;
}a[MAXN];
bool cmp(node a,node b)
{
	return a.date<b.date;
}
bool check(i128 mid,i128 x,int i)
{
	if(a[i].c>=0) return (a[i].b+mid*a[i].c+a[i].b+x*a[i].c)*(mid-x+1)>=2*a[i].a;
	else if(a[i].c<0)
	{
		if(x>=a[i].x) return (mid-x+1)>=a[i].a;
		else if(a[i].x<=mid) return (a[i].x-x)*(a[i].b+x*a[i].c+a[i].b+(a[i].x-1)*a[i].c)+2*(mid-a[i].x+1)>=2*a[i].a;
		else return (a[i].b+x*a[i].c+a[i].b+mid*a[i].c)*(mid-x+1)>=2*a[i].a;
	}
}
void dfsfa(int x,int fat)
{
	fa[x]=fat;
	for(int i=0;i<p[x].size();i++)
		if(p[x][i]!=fat)
			dfsfa(p[x][i],x);
}
bool check2(int mid)
{
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	{
		int l=1,r=mid,ans=-1;
		while(l<=r)
		{
			int midd=l+r>>1;
			if(check(mid,midd,i)) l=midd+1,ans=midd;
			else r=midd-1;
		}
		if(ans==-1) return 0;
		a[i].date=ans;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
		date[a[i].id]=a[i].date;
	int time=1; vis[1]=1;
	for(int i=1;i<=n;i++)
	{
		if(vis[a[i].id]) continue;
		vector< pair<int,int> > tmp;
		int j=a[i].id; tmp.push_back({j,date[j]});
		j=fa[j];
		while(!vis[j])
		{
			tmp.push_back({j,date[j]});
			j=fa[j];
		}
		//reverse(tmp.begin(),tmp.end());
		for(int k=tmp.size()-1;k>=0;k--)
		{
			if(time+1>tmp[k].se) return 0;
			time++;
			vis[tmp[k].fi]=1;
		}
	}
	return 1;
}
signed main()
{
	freopen("tree4.in","r",stdin);
	ios::sync_with_stdio(0);
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i].a=read();a[i].b=read();a[i].c=read(); a[i].id=i;
		if(a[i].c<0) a[i].x=ceil((1-a[i].b)*1.0/a[i].c);
	}
	for(int i=1;i<n;i++)
	{
		u=read();v=read();
		p[u].push_back(v);
		p[v].push_back(u);
	}
	dfsfa(1,0);
	int L=1,R=1000000000,ans=-1;
	while(L<=R)
	{
		int mid=L+R>>1;
		if(check2(mid)) ans=mid,R=mid-1;
		else L=mid+1;
	}
	printf("%lld",ans);
	return 0;
}

2024/6/8 12:12
加载中...