记录编号	558332	评测结果	AAAAAAAAAT
题目名称	[NOIP 2020]排水系统	最终得分	90
用户昵称	Satoshi	是否通过	未通过
代码语言	C++	运行时间	1.581 s
提交时间	2020-12-22 18:38:05	内存使用	3.49 MiB

#include <fstream>
//#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define N 100010
using namespace std;
ifstream cin("2020water.in");
ofstream cout("2020water.out");
typedef long long ll;
inline ll gcd(ll a, ll b)
{
    while(true)
    {
        if(!a)return b;
        if(!b)return a;
        if(a>b)a%=b;
        else b%=a;
    }
}
inline ll lcm(ll a, ll b)
{
    return a/gcd(a,b)*b;
}
class frac
{
    public:
        ll x,y;
    frac(){x=0;y=1;}
    frac(ll a){x=a;y=1;}
    frac(ll a, ll b){x=a;y=b;}
    inline frac simp()
    {
        ll k = gcd(x,y);
        return frac(x/k,y/k);
    }
    frac operator *(ll a){return frac(x*a,y).simp();}
    frac operator /(ll a){return frac(x,y*a).simp();}
    frac extend(ll k){return frac(x*(k/y),k);}
    frac operator +(frac a)
    {
        ll z = lcm(y,a.y);
        frac A = extend(z);
        frac B = a.extend(z);
        return frac(A.x+B.x,A.y).simp();
    }
    frac inv(){return frac(y,x);}
    frac operator *(frac a)
    {
        ll z = gcd(x,a.y);
        ll o = gcd(y,a.x);
        return frac((x/z)*(a.x/o),(y/o)*(a.y/z)).simp();
    }
    frac operator /(frac a){return (*this) * a.inv();}
    void print(){cout<<x<<' '<<y;}
};
int n,m;
vector<int> G[N];
vector<int> O;
frac f[N];
bool vis[N];
int deg[N];
int indeg[N];
void read()
{
    cin>>n>>m;
    int i,j,k,u;
    for(i=1;i<=n;i++)
    {
        cin>>k;
        deg[i]=k;
        for(j=1;j<=k;j++)
        {
            cin>>u;
            G[i].push_back(u);
            indeg[u]++;
        }
        if(!k)O.push_back(i);
    }
    for(i=1;i<=m;i++)
    {
        G[0].push_back(i);
        indeg[i]++;
    }
    f[0] = frac(m,1);
    deg[0] = m;
}
vector<int> p;
void BFS()
{
    queue<int> q;
    
    q.push(0);
    vis[0]=1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        p.push_back(u);
        for(int i=0;i<G[u].size();i++)
        {
            int v = G[u][i];
            indeg[v]--;
            if(!indeg[v])q.push(v);
            /*f[v] = f[v] + (f[u]/deg[u]);
            if(!vis[v])
            {
                vis[v]=1;
                q.push(v);
            }*/
        }
    }
    for(int i=0;i<p.size();i++)
    {
        int u = p[i];
        for(int j=0;j<G[u].size();j++)
        {
            int v = G[u][j];
            f[v] = f[v] + (f[u]/deg[u]);
        }
    }
}
void work()
{
    BFS();
    //cout<<"fuck"<<endl;
    for(int i=0; i < O.size();i++)
    {
        f[O[i]].print();
        cout<<endl;
    }
}
int main()
{
    //frac ans = frac(3,7)/frac(9,14);
    //ans.print();
    read();
    work();
    return 0;
}