Submission #930386

#	Time	Username	Problem	Language	Result	Execution time	Memory
930386		boris_mihov	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	11 ms	22108 KiB

joitter2

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <set>
#include <map>

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

int n, m;
llong answer;
struct DSU
{
    int sz[MAXN];
    int par[MAXN];
    std::map <int,int> fromComp[MAXN];
    std::set <int> pointingNodes[MAXN];
    std::set <int> fromNode[MAXN];
    std::set <int> nodes[MAXN];

    void build()
    {
        std::fill(sz + 1, sz + 1 + n, 1);
        std::iota(par + 1, par + 1 + n, 1);
        for (int i = 1 ; i <= n ; ++i)
        {
            nodes[i].insert(i);
        }
    }

    int find(int node)
    {
        if (par[node] == node) return node;
        return par[node] = find(par[node]);
    }

    void addEdge(int u, int v)
    {
        int cU = find(u);
        int cV = find(v);
        if (cU == cV) 
        {
            return;
        }

        if (fromNode[u].count(cV))
        {
            return;
        }

        if (!fromComp[cV].count(cU))
        {
            answer += nodes[cV].size();
            pointingNodes[cV].insert(u);
            fromNode[u].insert(cV);
            fromComp[cU][cV]++;
            return;
        }
        
        answer -= 1LL * fromComp[cV][cU] * nodes[cU].size();
        answer -= 1LL * fromComp[cU][cV] * nodes[cU].size();
        answer += 2LL * nodes[cU].size() * nodes[cV].size();

        if (nodes[cV].size() > nodes[cU].size())
        {
            std::swap(u, v);
            std::swap(cV, cU);
        }

        std::queue <int> waitlist;
        for (const int &node : pointingNodes[cV])
        {
            if (nodes[cU].count(node))
            {
                waitlist.push(node);
            }
        }

        for (const int &node : nodes[cV])
        {
            if (fromNode[node].count(cU))
            {
                pointingNodes[cU].erase(pointingNodes[cU].find(node));
                fromNode[node].erase(fromNode[node].find(cU));
            }
        }

        fromComp[cU][cV] = 0;
        fromComp[cV][cU] = 0;
        while (waitlist.size())
        {
            pointingNodes[cV].erase(pointingNodes[cV].find(waitlist.front()));
            waitlist.pop();
        }

        answer -= 1LL * nodes[cV].size() * pointingNodes[cV].size();
        for (const int &node : pointingNodes[cV])
        {
            fromNode[node].erase(fromNode[node].find(cV));
            fromComp[find(node)][cV]--;

            bool inserted = pointingNodes[cU].insert(node).second;
            if (inserted) 
            {
                answer += nodes[cU].size();
                fromNode[node].insert(cU);
                fromComp[find(node)][cU]++;
            }
        }
        
        answer += 1LL * pointingNodes[cU].size() * nodes[cV].size();
        for (const auto &[key, value] : fromComp[cV])
        {
            fromComp[cU][key] += value;
        }

        for (const int &node : nodes[cV])
        {
            nodes[cU].insert(node);
        }

        par[cV] = cU;
    }
};

DSU dsu;
int from[MAXM];
int to[MAXM];
void solve()
{
    dsu.build();
    for (int i = 1 ; i <= m ; ++i)
    {
        dsu.addEdge(from[i], to[i]);
        std::cout << answer << '\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;
}

/*
14 13
10 14
3 10
14 13
1 3
3 5
3 11
12 14
14 6
11 8
2 3
7 8
9 7
1 4

5 6
4 2
1 5
2 3
2 5
3 2
3 1
*/

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