这是蒟蒻的考场代码,大样例过了,还对拍过一会(因为急着写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;
}