Submission #684310

#	Time	Username	Problem	Language	Result	Execution time	Memory
684310		finn__	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	971 ms	64772 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

set<unsigned> g[100000], rg[100000], pre[100000];
int d[100000];
queue<pair<unsigned, unsigned>> q;
int64_t x = 0;

int representant(int u)
{
    return d[u] < 0 ? u : (d[u] = representant(d[u]));
}

size_t total_edge_count(unsigned u)
{
    return g[u].size() + rg[u].size() + pre[u].size();
}

void insert_weak_connection(unsigned u, unsigned v)
{
    g[u].insert(v);
    rg[v].insert(u);
    if (g[v].find(u) != g[v].end())
        q.emplace(u, v);
}

void merge(unsigned u, unsigned v)
{
    if (u == v)
        return;

    if (total_edge_count(u) < total_edge_count(v)) // Make u the larger component.
        swap(u, v);

    x -= d[u] * pre[v].size() + d[v] * pre[u].size();
    d[u] += d[v];
    d[v] = u;

    for (unsigned const &y : pre[v])
        if (pre[u].find(y) != pre[u].end())
            x += d[u];
        else
            pre[u].insert(y);

    g[u].erase(v);
    g[v].erase(u);
    rg[u].erase(v);
    rg[v].erase(u);

    for (unsigned const &y : g[v])
    {
        rg[y].erase(v);
        insert_weak_connection(u, y);
    }
    for (unsigned const &y : rg[v])
    {
        g[y].erase(v);
        insert_weak_connection(y, u);
    }
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    size_t n, m;
    cin >> n >> m;

    for (unsigned i = 0; i < n; i++)
    {
        d[i] = -1;
        pre[i].insert(i);
    }

    for (size_t i = 0; i < m; i++)
    {
        unsigned u, v;
        cin >> u >> v;
        u--, v--;

        v = representant(v);
        if (representant(u) != v && pre[v].find(u) == pre[v].end())
        {
            pre[v].insert(u);
            x -= d[v];
            u = representant(u);
            insert_weak_connection(u, v);

            while (!q.empty())
            {
                auto const [a, b] = q.front();
                q.pop();
                merge(representant(a), representant(b));
            }
        }
        cout << x << '\n';
    }
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:82:29: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   82 |         if (representant(u) != v && pre[v].find(u) == pre[v].end())
      |             ~~~~~~~~~~~~~~~~^~~~

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