제출 #684305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684305		finn__	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	703 ms	1048576 KiB

joitter2

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

vector<set<unsigned>> g, rg, pre;
vector<int> d;
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()
{
    size_t n, m;
    cin >> n >> m;

    g = vector<set<unsigned>>(n);
    rg = vector<set<unsigned>>(n);
    pre = vector<set<unsigned>>(n);
    d = vector<int>(n, -1);

    for (unsigned i = 0; i < n; i++)
        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())
            {
                merge(q.front().first, q.front().second);
                q.pop();
            }
        }
        cout << x << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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