你说得对,但是我又悬赏4关
查看原帖
你说得对,但是我又悬赏4关
540363
AKPC楼主2023/8/11 13:51

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

*/
2023/8/11 13:51
加载中...