Submission #863023

#	Time	Username	Problem	Language	Result	Execution time	Memory
863023		boris_mihov	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	2 ms	12632 KiB

joitter2

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXM = 300000 + 10;
const int INF  = 1e9;

int n, m;
int compCnt;
int inComp[MAXN];
int compSZ[MAXN];
bool addedEdge[MAXN];
std::vector <int> g[MAXN];
std::vector <int> rev[MAXN];
std::vector <int> inSCC[MAXN];
std::vector <int> dag[MAXN];
std::stack <int> topSort;
bool vis[MAXN];
int from[MAXM];
int to[MAXM];

void topSortDFS(int node)
{
    vis[node] = true;
    for (const int &u : g[node])
    {
        if (!vis[u])
        {
            topSortDFS(u);
        }
    }

    topSort.push(node);
}

void sccDFS(int node)
{
    vis[node] = true;
    inComp[node] = compCnt;
    inSCC[compCnt].push_back(node);
    compSZ[compCnt]++;

    for (const int &u : rev[node])
    {
        if (vis[u]) continue;
        sccDFS(u);
    }
}

llong solveDFS(int node)
{
    vis[node] = true;
    llong res = (1LL * compSZ[node] * (compSZ[node] - 1));
    for (const int &u : dag[node])
    {
        if (!vis[u])
        {
            res += solveDFS(u);
        }

        res += compSZ[u];
    }

    return res;
}

llong calcANS()
{
    compCnt = 0;
    std::fill(vis + 1, vis + 1 + n, false);
    std::fill(inComp + 1, inComp + 1 + n, 0);
    std::fill(compSZ + 1, compSZ + 1 + n, 0);

    for (int i = 1 ; i <= n ; ++i)
    {
        inSCC[i].clear();
        dag[i].clear();
    }   

    std::vector <int> tops;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (!vis[i])
        {
            topSortDFS(i);
            tops.push_back(topSort.top());
        }
    }

    std::fill(vis + 1, vis + 1 + n, false);
    while (!topSort.empty())
    {
        int node = topSort.top();
        topSort.pop();

        if (!vis[node])
        {
            compCnt++;
            sccDFS(node);   
        }
    }

    for (int i = 1 ; i <= compCnt ; ++i)
    {
        for (const int &node : inSCC[i])
        {
            addedEdge[i] = true;
            for (const int &u : g[node])
            {
                if (addedEdge[inComp[u]]) continue;
                dag[i].push_back(inComp[u]);
                addedEdge[inComp[u]] = true;
            }

            for (const int &u : g[node])
            {
                addedEdge[inComp[u]] = false;
            }

            addedEdge[i] = false;
        }
    }

    std::fill(vis + 1, vis + 1 + n, false);
    std::reverse(tops.begin(), tops.end());
    llong ans = 0;
    for (const int &node : tops)
    {
        if (!vis[node])
        {
            ans += solveDFS(inComp[node]);
        }
    }

    return ans;
}

void solve()
{
    for (int i = 1 ; i <= m ; ++i)
    {
        g[from[i]].push_back(to[i]);
        rev[to[i]].push_back(from[i]);
        std::cout << calcANS() << '\n';
    }
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> from[i] >> to[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83