求助__int128相关,原代码long long60pts
查看原帖
求助__int128相关,原代码long long60pts
538738
ttttalk楼主2023/11/3 19:22

然后加了之后就获得了零分的好成绩!


#include<cstdio>
#include<iostream>
#include<cstring>
#define int __int128
using namespace std;
const int N=1e5+10;
int n,m,h[N],son[N],tot;
int rd()
{
	char c=getchar();
	int f=1,r=0;
	while (c<'0'||c>'0')
	{
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		r=r*10+c-'0';
		c=getchar();
	}
	return r*f;
}
struct edge{
	int v,nxt;
}e[N];
struct frac{
	int s,m;
	void clear()
	{
		s=m=0;
	}
}a[N],res[N];
void add(int u,int v)
{
	e[++tot].v=v;
	e[tot].nxt=h[u];
	h[u]=tot;
}
int gcd(int a,int b)
{
	if (a<b) swap(a,b);
	if (a%b==0) return b;
	while (b!=0)
	{
		if (a%b==0) return b;
		swap(a,b);b=b%a;
	}
	return a;
}
frac get_ans(frac a,frac b)
{
	if (a.m==0) return b;
	int dd=gcd(a.m,b.m);
	int lcm=a.m*b.m/dd;
	frac c;
	c.m=lcm,c.s=a.s*(lcm/a.m)+b.s*(lcm/b.m);
	int qq=gcd(c.m,c.s);
	if (qq!=1) c.m/=qq,c.s/=qq;
	return c;
}
void dfs(int u)
{
	if (!h[u])
	{
		res[u]=get_ans(res[u],a[u]);
		a[u].m=1,a[u].s=0;
		return;
	}
	frac t=a[u];
	t.m*=son[u];
	for (int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		a[v]=get_ans(a[v],t);
		dfs(v);
	}
	a[u].clear();
}
void print(int a)
{
	if (a<0) putchar('-'),a=-a;
	if (a>9) print(a/10);
	putchar(a%10+'0');
}
signed main()
{
//	freopen("P7113_7.in","r",stdin);
//	freopen("qwq.out","w",stdout);
//	cin.tie(0),cout.tie(0);
//	__int128 sss=rd();
//	print(sss);
	n=rd(),m=rd();
	int v;
	for (int i=1;i<=n;i++)
	{
		res[i].clear();
		son[i]=rd();
		for (int j=1;j<=son[i];j++)
		{
			v=rd();
			add(i,v);
		}
	}
	for (int i=1;i<=m;i++)
	{
		for (int j=1;j<=n;j++) a[j].clear();
		a[i].s=a[i].m=1;
		dfs(i);
	}
	for (int i=1;i<=n;i++)
	{
		if (!h[i])
		{
			print(res[i].s);
			cout<<" ";
			print(res[i].m);
			cout<<"\n";
		}
	}
}

2023/11/3 19:22
加载中...