求助noipT1……
查看原帖
求助noipT1……
132290
开始新的记忆楼主2020/12/6 08:59

这是蒟蒻的考场代码,大样例过了,还对拍过一会(因为急着写T3就没怎么管T1了)然后洛谷和oitiku都30。。。。我爆炸了,求hack,我想知道我错哪里了(都是WA)

#include<bits/stdc++.h>
using namespace std;
#define ll  long long
ll p[100010],q[100010],ansp[100010],ansq[100010];
vector <int > con[100010];
int n,m,d[100010];
bool vis[100010];

ll gcd(ll a,ll b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}

void add1(ll p1,ll q1,int pos)
{
	if(q[pos]==0)
	{
		p[pos]=p1,q[pos]=q1;
		return;
	}
	ll qwq=gcd(q1,q[pos]);
	ll lcm=q1*q[pos]/qwq;
	ll ans1=lcm/q1,ans2=lcm/q[pos];
	p1*=ans1,q1=lcm;
	p[pos]*=ans2,q[pos]=lcm;
	p[pos]+=p1;
	ll az=gcd(p[pos],q[pos]);
	p[pos]/=az,q[pos]/=az;
}

void add2(ll p1,ll q1,int pos)
{
	if(ansq[pos]==0)
	{
		ansp[pos]=p1,ansq[pos]=q1;
		return;
	}
	ll qwq=gcd(q1,ansq[pos]);
	ll lcm=q1*ansq[pos]/qwq;
	ll ans1=lcm/q1,ans2=lcm/ansq[pos];
	p1*=ans1,q1=lcm;
	ansp[pos]*=ans2,ansq[pos]=lcm;
	ansp[pos]+=p1;
	ll az=gcd(ansp[pos],ansq[pos]);
	ansp[pos]/=az,ansq[pos]/=az;
}

void bfs(int s)
{
	memset(vis,0,sizeof(vis));
	queue <int > qu;
	qu.push(s);vis[s]=1;
	while(!qu.empty())
	{
		int x=qu.front();
		qu.pop();
		for(int i=0;i<con[x].size();++i)
		{
			add1(p[x],(ll)q[x]*con[x].size(),con[x][i]);
			if(!vis[con[x][i]])
			{
				if(!d[con[x][i]])
					continue;
				vis[con[x][i]]=1;
				qu.push(con[x][i]);
			}
		}
		q[x]=0,p[x]=0;
	}
}

int main()
{	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&d[i]);
		for(int j=1,x;j<=d[i];++j)
		{
			scanf("%d",&x);
			con[i].push_back(x);
		}
	}
	for(int i=1;i<=m;++i)
	{
		p[i]=q[i]=1ll;
		bfs(i);
		for(int j=1;j<=n;++j)
			if(d[j] && p[j])
				bfs(j); 
		for(int j=1;j<=n;++j)
			if(p[j])
				add2(p[j],q[j],j),p[j]=0,q[j]=0;
	}
	for(int i=1;i<=n;++i)
		if(ansp[i])
			printf("%lld %lld\n",ansp[i],ansq[i]);
	return 0;
}
2020/12/6 08:59
加载中...