1836F - Doctor's Brown Hypothesis - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
int n, m;
int dfn[N], low[N], d[N];
int st[N], top, tot, g[N];
bool in[N];
long long k, ans;
vector<int> to[N];
int sum[N];

int gcd(int n, int m) { return !m ? n : gcd(m, n % m); }

void dfs(int i)
{
    low[i] = dfn[i] = ++tot;
    st[++top] = i, in[i] = 1;

    for (int j : to[i])
    {
        if (!dfn[j])
        {
            d[j] = d[i] + 1;
            dfs(j);
            low[i] = min(low[i], low[j]);
            continue;
        }

        if (!in[j])
        {
            continue;
        }

        low[i] = min(low[i], low[j]);
        g[i] = gcd(g[i], abs(d[i] + 1 - d[j]));
    }

    if (low[i] == dfn[i])
    {
        int len = 0, x;
        vector<int> tp;
        do
        {
            x = st[top--];
            in[x] = 0;
            len = gcd(len, g[x]);
            tp.push_back(x);
        } while (x != i);

        if (len == 0)
        {
            return;
        }

        int gu = k % len;
        for (int j : tp)
        {
            sum[d[j] % len]++;
        }

        if (!gu)
        {
            for (int t = 0; t != len; t++)
            {
                int x = sum[t];
                ans += 1ll * x * (x + 1) / 2;
            }
        }
        else if (gu * 2 == len)
        {
            for (int t = 0; t != gu; t++)
            {
                ans += 1ll * sum[t] * sum[(t + gu) % len];
            }
        }

        for (int t = 0; t != len; t++)
        {
            sum[t] = 0;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> m >> k;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        to[x].push_back(y);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
        {
            dfs(i);
        }
    }

    cout << ans << endl;
}