做着玩
T1 排水系统
带有多个起点的DAG，可以对于每个起点dfs来计算起点到各个终点的路径的后继结点个数的积，即每个起点对于每个终点所产生的贡献，但是没想到此题在考场上的数据是卡ull的，开了ll是70pts，ull是80pts，最终用了__uint128_t+输出优化才100pts，但是实际上还是可以被卡掉的，正解需要高精度
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<cstdio> #include<algorithm> #include<iostream> using namespace std; #define N 100010 typedef __uint128_t LL; int n,m,cnt,h[N],num[N]; LL sum; struct data { int to,next; }edge[N*5]; struct Ans { LL p,q; }a[N]; bool vis[N]; void add(int u,int v) { edge[++cnt]=(data){v,h[u]},h[u]=cnt; } LL gcd(LL x,LL y) { return !y?x:gcd(y,x%y); } void dfs(int x) { if (num[x]) sum*=(LL)num[x]; vis[x]=true; bool mark=false; for (int i=h[x];i;i=edge[i].next) if (!vis[edge[i].to]) dfs(edge[i].to),mark=true; if (!mark) if (!a[x].p && !a[x].q) a[x]=(Ans){1LL,(LL)sum}; else { LL son=a[x].p*sum+a[x].q,mo=a[x].q*sum; a[x]=(Ans){son/gcd(son,mo),mo/gcd(son,mo)}; } if (num[x]) sum/=(LL)num[x]; vis[x]=false; } void write(LL x) { if (x>9) write(x/10); putchar(x%10+'0'); } int main() { int x; scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) { scanf("%d",&num[i]); for (int j=1;j<=num[i];++j) scanf("%d",&x),add(i,x); } for (int i=1;i<=m;++i) sum=1LL,dfs(i); for (int i=1;i<=n;++i) if (!num[i]) write(a[i].p),cout<<" ",write(a[i].q),cout<<endl; return 0; } |