rt,两份代码,区别仅在于一个用的是 long double
一个是 __int128
。第一份 80pts ,第二份 AC 。
但是话说 long double
不是可以存到 10308 吗?
//80pts,long double.
#include<bits/stdc++.h>
#define db long double
using namespace std;
db GCD(db a,db b){
if(a<b)swap(a,b);
if(b==0)return a;
db l(0),r(a/b+1),k;
while(l<=r){
db mid(floor((l+r)/2));
if(b*mid<=a)k=mid,l=mid+1;
else r=mid-1;
}
return GCD(b,a-k*b);
//GCD(b,a%b)=GCD(b,a-(a/b)*b).
}
const int mxN(1e5);
int n,m,in[mxN+5],out[mxN+5];
vector<int>nd[mxN+5];
struct Val{db p,q;}val[mxN+5];//1/1 or 0/1.
void add(int u,int v){nd[u].push_back(v),++in[v],++out[u];}
void pls(int u,int v){//结点v加上结点u.
if(val[u].q==0)return;
db LCM(val[u].q*val[v].q/GCD(val[u].q,val[v].q)),P,Q;
P=(val[v].p*(LCM/val[v].q)+val[u].p*(LCM/val[u].q)),Q=LCM;
db gcd=GCD(P,Q);
P/=gcd,Q/=gcd,val[v].p=P,val[v].q=Q;
}
void DAG(){
queue<int>q;
for(int u(1);u<=n;++u)if(!in[u])q.push(u),val[u].p=val[u].q=1;else val[u].p=0,val[u].q=1;
while(!q.empty()){
int u(q.front());q.pop();
if(nd[u].size()!=0){
val[u].q*=(db)nd[u].size();
db gcd(GCD(val[u].p,val[u].q));
val[u].p/=gcd,val[u].q/=gcd;
}
for(int i(0);i<nd[u].size();++i){
int v(nd[u][i]);pls(u,v);
if(!(--in[v]))q.push(v);
}
}
}
int main(){
// freopen("water3.in","r",stdin);
// freopen("me.out","w",stdout);
scanf("%d%d",&n,&m);
for(int u(1),s;u<=n;++u){
scanf("%d",&s);
for(int i(1),v;i<=s;++i)scanf("%d",&v),add(u,v);
}
DAG();
for(int u(1);u<=n;++u)if(!out[u])printf("%.0Lf %.0Lf\n",val[u].p,val[u].q);
return 0;
}
//100pts,__int128.
#include<bits/stdc++.h>
#define intll __int128
using namespace std;
intll GCD(intll a,intll b){
if(a<b)swap(a,b);
if(b==0)return a;
intll l(0),r(a/b+1),k;
while(l<=r){
intll mid(((l+r)/2));
if(b*mid<=a)k=mid,l=mid+1;
else r=mid-1;
}
return GCD(b,a-k*b);
//GCD(b,a%b)=GCD(b,a-(a/b)*b).
}
void print(intll x){if(x>9)print(x/10);putchar(x%10+48);}
const int mxN(1e5);
int n,m,in[mxN+5],out[mxN+5];
vector<int>nd[mxN+5];
struct Val{intll w1,w2;}val[mxN+5];//1/1 or 0/1.
void add(int u,int v){nd[u].push_back(v),++in[v],++out[u];}
void pls(int u,int v,intll x){//结点v加上结点u的1/x.
intll wu1(val[u].w1),wu2(val[u].w2),wv1(val[v].w1),wv2(val[v].w2),gcd;
gcd=(GCD(wu1,x)),wu1/=gcd,x/=gcd,
wu2*=x;
val[v].w1=wu1*wv2+wu2*wv1,val[v].w2=wu2*wv2;
gcd=GCD(val[v].w1,val[v].w2);
val[v].w1/=gcd,val[v].w2/=gcd;
}
void DAG(){
queue<int>q;
for(int u(1);u<=n;++u)if(!in[u])q.push(u),val[u].w1=val[u].w2=1;else val[u].w1=0,val[u].w2=1;
while(!q.empty()){
int u(q.front());q.pop();
for(int i(0);i<nd[u].size();++i){
int v(nd[u][i]);
pls(u,v,1.0*nd[u].size());
if(!(--in[v]))q.push(v);
}
}
}
int main(){
// freopen("water3.in","r",stdin);
// freopen("me.out","w",stdout);
scanf("%d%d",&n,&m);
for(int u(1),s;u<=n;++u){
scanf("%d",&s);
for(int i(1),v;i<=s;++i)scanf("%d",&v),add(u,v);
}
DAG();
for(int u(1);u<=n;++u)if(!out[u])print(val[u].w1),putchar(' '),print(val[u].w2),putchar('\n');
return 0;
}
Tips:
//本地测 long double 范围的代码 #include<bits/stdc++.h> using namespace std; int main(){ long double a; a=1e308,cout<<a<<endl; a=1e309,cout<<a<<endl; return 0; } /* output: 1e+308 inf */