Submission #1188743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188743		0x34c	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	100 / 100	866 ms	178372 KiB

joitter2

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define endl '\n'
#define int ll

using namespace std;

class DSU
{
private:
    vector<int> par;

public:
    // 0 = in, 1 = out
    vector<set<tiii>> deg;
    vector<int> cnt, indeg;
    int edges = 0;

    DSU(int n)
    {
        par.resize(n, 0);
        cnt.resize(n, 1);
        deg.resize(n);
        indeg.resize(n, 0);
        iota(par.begin(), par.end(), 0);
    }

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

    bool uni(int a, int b)
    {
        a = find(a);
        b = find(b);

        if (a == b)
            return false;

        if (deg[a].size() < deg[b].size())
            swap(a, b);

        vector<pii> unis;
        int delta = 0;
        int delta_a = 0;
        int delta_b = 0;

        vector<pair<int, tiii>> rem, ins;
        for (auto [v, t, p] : deg[b])
        {
            if (find(v) == a)
            {
                if (t == 0 && p != -1)
                {
                    edges -= cnt[b];
                    delta_a++;
                }
                else if (p != -1)
                {
                    edges -= cnt[a];
                    delta_b++;
                }

                rem.push_back({a, {b, t ^ 1, p}});
                rem.push_back({b, {v, t, p}});
                continue;
            }

            if (t == 0 && p != -1)
            {
                if (!deg[a].count({v, 0, p}))
                    edges += cnt[a];
                else
                    delta++;
            }

            ins.push_back({a, {v, t, p}});
            rem.push_back({v, {b, t ^ 1, p}});
            ins.push_back({v, {a, t ^ 1, p}});
        }

        edges += (indeg[a] - delta - delta_b) * cnt[b];
        indeg[a] += indeg[b] - delta - delta_a - delta_b;
        indeg[b] = 0;

        edges += 2 * cnt[a] * cnt[b];
        par[b] = a;
        cnt[a] += cnt[b];

        for (auto x : rem)
            deg[x.first].erase(x.second);

        for (auto x : ins)
        {
            deg[x.first].insert(x.second);

            int v = x.first, u = get<0>(x.second);
            if (get<2>(x.second) == -1 && deg[v].count({u, 1, -1}) && deg[u].count({v, 1, -1}))
                unis.push_back({v, u});
        }

        for (pii &p : unis)
            uni(p.first, p.second);

        return true;
    }

    void insert_edge(int a, int b)
    {
        if (find(a) == find(b))
            return;
        b = find(b);

        if (deg[find(a)].count({b, 1, a}))
            return;

        edges += cnt[b];
        deg[find(a)].insert({b, 1, a});
        deg[find(a)].insert({b, 1, -1});
        deg[b].insert({find(a), 0, a});
        deg[b].insert({find(a), 0, -1});
        a = find(a);
        indeg[b]++;

        if (deg[a].count({b, 1, -1}) && deg[b].count({a, 1, -1}))
            uni(a, b);
    }
};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    DSU dsu(N);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;

        dsu.insert_edge(a, b);
        cout << dsu.edges << endl;
    }
}

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