Submission #1250237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250237		chikien2009	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	100 / 100	856 ms	103896 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int par[100000], n, m, a, b;
long long sz[100000], res;
set<int> c[100000], g[100000], r[100000];
deque<pair<int, int>> edge;

inline int Get(int inp)
{
    return (inp == par[inp] ? inp : par[inp] = Get(par[inp]));
}

inline void Check(int ina, int inb)
{
    g[ina].insert(inb);
    r[inb].insert(ina);
    if (g[inb].find(ina) != g[inb].end())
    {
        edge.push_back({ina, inb});
    }
}

inline int all(int inp)
{
    return c[inp].size() + g[inp].size() + r[inp].size();
}

inline void Combine(int ina, int inb)
{
    ina = Get(ina);
    inb = Get(inb);
    if (ina == inb)
    {
        return;
    }
    if (all(ina) < all(inb))
    {
        swap(ina, inb);
    }
    res += sz[ina] * c[inb].size() + sz[inb] * c[ina].size(); // part of A to child B and reverse
    sz[ina] += sz[inb];
    par[inb] = ina;
    for (auto & i : c[inb])
    {
        if (c[ina].find(i) != c[ina].end()) 
        // if this node is child of both A and B, they're counted twice from above
        {
            res -= sz[ina];
        }
        else
        {
            c[ina].insert(i);
        }
    }
    g[ina].erase(inb);
    g[inb].erase(ina);
    r[ina].erase(inb);
    r[inb].erase(ina);
    for (auto & i : g[inb])
    {
        r[inb].erase(i);
        Check(ina, i);
    }
    for (auto & i : r[inb])
    {
        g[inb].erase(i);
        Check(i, ina);
    }
}

int main()
{
    setup();

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        par[i] = i;
        sz[i] = 1;
        c[i] = {i};
    }
    while (m--)
    {
        cin >> a >> b;
        a--;
        b--;
        b = Get(b);
        if (Get(a) != b && c[b].find(a) == c[b].end())
        {
            c[b].insert(a);
            res += sz[b];
            a = Get(a);
            Check(a, b);
            while (!edge.empty())
            {
                Combine(edge.front().first, edge.front().second);
                edge.pop_front();                
            }
        }
        cout << res << "\n";
    }
    return 0;
}

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