Submission #895184

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

joitter2

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

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::set <int> in[MAXN];
    std::set <int> out[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)
    {
        if (find(u) == find(v)) 
        {
            return;
        }

        if (!in[find(u)].count(v))
        {
            if (out[u].count(find(v)))
            {
                return;
            }

            answer += sz[find(v)];
            out[u].insert(find(v));
            in[find(v)].insert(u);
            return;
        }

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

        for (const int &node : nodes[u])
        {
            if (out[node].count(v))
            {
                answer -= sz[v];
                out[node].erase(out[node].find(v));
                in[v].erase(in[v].find(node));
            }
        }

        std::queue <int> toErase;
        std::queue <int> toErase2;
        for (const int &node : in[u])
        {
            if (find(node) == v)
            {
                toErase.push(node);
            } else
            {
                toErase2.push(node);
            }
        }

        while (toErase.size())
        {
            int top = toErase.front();
            toErase.pop();

            answer -= sz[u];
            in[u].erase(in[u].find(top));
            out[top].erase(out[top].find(u));
        }

        answer += 1LL * in[v].size() * sz[u];
        while (toErase2.size())
        {
            int top = toErase2.front();
            toErase2.pop();

            in[u].erase(in[u].find(top));
            out[top].erase(out[top].find(u));
            in[v].insert(top);
            out[top].insert(v);
            answer += sz[v] - sz[u];
        }

        answer += 2LL * sz[v] * sz[u];
        sz[v] += sz[u];
        par[u] = v;
    }
};

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

*/

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