拓扑int128 WA80pts 求条
查看原帖
拓扑int128 WA80pts 求条
529247
BLX32M_10楼主2024/8/1 20:15
#include <bits/stdc++.h>
using namespace std;
__int128_t gcd(__int128_t x, __int128_t y)
{
    while (y)
    {
        __int128_t t = x % y;
        x = y, y = t;
    }
    return x;
}
struct frac
{
    __int128_t p = 0, q = 1;
    void mt()
    {
        __int128_t g = gcd(p, q);
        p /= g;
        q /= g;
    }
    const frac operator + (const frac xx) const
    {
        frac x;
        x.p = xx.p;
        x.q = xx.q;
        __int128_t g = x.q / gcd(q, x.q) * q;
        frac res;
        res.p += x.p * (g / x.q);
        res.p += p * (g / q);
        res.q = g;
        res.mt();
        return res;
    }
} a[100005];
vector <int> ed[100005], ft[100005]; //ft 返图
int rd[100005], topo[100005], num;
inline void write(__int128_t x)
{
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int main()
{
    int n, m;
    int st = -1;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        a[i].q = 1, a[i].p = 0;
        int d;
        scanf("%d", &d);
        while (d--)
        {
            int x;
            scanf("%d", &x);
            ed[i].push_back(x);
            ft[x].push_back(i);
            rd[x]++;
        }
    }
    for (int i = 1; i <= n; i++)
        if (rd[i] == 0)
        {
            st = i;
            a[i].p = 1;
        }
    queue <int> q;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        topo[++num] = u;
        for (int v : ed[u])
        {
            rd[v]--;
            if (rd[v] == 0)
            {
                for (int x : ft[v])
                {
                    frac cc = a[x];
                    cc.q *= ed[x].size();
                    cc.mt();
                    a[v] = a[v] + cc;
                }
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; i++)
        if (ed[i].size() == 0)
        {
            write(a[i].p);
            putchar(' ');
            write(a[i].q);
            putchar('\n');
        }
    return 0;
}
2024/8/1 20:15
加载中...