oj.uz

답안 #684309

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684309 2023-01-20T20:59:34 Z finn__ 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 487 ms 1048576 KB 
#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(a, b);
            }
        }
        cout << x << '\n';
    }
}

Compilation message

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
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14440 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Runtime error 487 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14440 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Runtime error 487 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14440 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Runtime error 487 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -