80 pts 玄学错误,样例以及大样例过,但是 WA 2 个点
考场代码:
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
inline int read(){
int x=0;bool f=1;register char c=getchar();
while(c<48||c>57){if(c=='-') f=0;c=getchar();}
while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
#define lcm(x,y) (x)*(y)/gcd((x),(y))
inline int gcd(int a,int b){
if (b==0) return a;
return gcd(b,a%b);
}
inline pair<int,int> fs_equal(int a,int b,int c){
if (a==0&&b==0) return make_pair(0,0);
b*=c;
int gc=gcd(a,b);
a/=gc,b/=gc;
return make_pair(a,b);
}
inline void fs_clac(int &a,int &b,int c,int d){
if (a==0&&b==0) {a=c,b=d;return;}
int lc=lcm(b,d),e=a,f=c;
e*=lc/b,f*=lc/d;
a=e+f,b=lc;
int gc=gcd(a,b);
a/=gc,b/=gc;
}
int n,m,k,x,cnt,fs[200005][2],rd[200005];
vector<int>e[200005];
bool tmp[200005];
signed main(){
n=read(),m=read();
for (register int i=1;i<=n;i++){
k=read();
if (k==0) tmp[i]=1;
while (k--) x=read(),e[i].push_back(x),rd[x]++;
}
for (register int i=1;i<=n;i++) if (rd[i]==0) fs[i][0]=1,fs[i][1]=1;
while (cnt<n){
// cout<<"Phigros\n";
for (register int i=1;i<=n;i++){
if (rd[i]!=0) continue;
// cout<<"Genshin "<<e[i].size()<<'\n';
pair<int,int>Pair=fs_equal(fs[i][0],fs[i][1],e[i].size());
int o=Pair.first,p=Pair.second;
for (register int j=0;j<e[i].size();j++){
int apc=e[i][j];
fs_clac(fs[apc][0],fs[apc][1],o,p);
rd[apc]--;
}
cnt++;
// cout<<i<<'\n';
}
}
for (register int i=1;i<=n;i++) if (tmp[i]) write(fs[i][0]),putchar(' '),write(fs[i][1]),putchar('\n');
return 0;
}
/*
10 1
5 2 3 4 5 6
2 7 8
2 8 10
2 9 7
1 9
3 7 8 9
1 10
0
1 10
0
*/