oj.uz

답안 #930389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930389 2024-02-19T14:10:17 Z boris_mihov 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 24 ms 44624 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <set>
#include <map>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXM = 300000 + 10;
const int MOD = 1e9 + 7;

int n, m;
llong answer;
struct DSU
{
    int sz[MAXN];
    int par[MAXN];
    std::map <int,int> fromComp[MAXN];
    std::set <int> pointingNodes[MAXN];
    std::set <int> fromNode[MAXN];
    std::set <int> nodes[MAXN];

    void build()
    {
        std::fill(sz + 1, sz + 1 + n, 1);
        std::iota(par + 1, par + 1 + n, 1);
        for (int i = 1 ; i <= n ; ++i)
        {
            nodes[i].insert(i);
        }
    }

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

    void merge(int cU, int cV)
    {
        cU = find(cU);
        cV = find(cV);
        if (cU == cV)
        {
            return;
        }

        answer -= 1LL * fromComp[cV][cU] * nodes[cU].size();
        answer -= 1LL * fromComp[cU][cV] * nodes[cV].size();
        answer += 2LL * nodes[cU].size() * nodes[cV].size();

        if (nodes[cV].size() > nodes[cU].size())
        {
            std::swap(cV, cU);
        }

        std::queue <int> waitlist;
        for (const int &node : pointingNodes[cV])
        {
            if (nodes[cU].count(node))
            {
                waitlist.push(node);
            }
        }

        for (const int &node : nodes[cV])
        {
            if (fromNode[node].count(cU))
            {
                pointingNodes[cU].erase(pointingNodes[cU].find(node));
                fromNode[node].erase(fromNode[node].find(cU));
            }
        }

        fromComp[cU][cV] = 0;
        fromComp[cV][cU] = 0;
        while (waitlist.size())
        {
            pointingNodes[cV].erase(pointingNodes[cV].find(waitlist.front()));
            waitlist.pop();
        }

        std::queue <std::pair <int,int>> toMerge;
        for (const int &node : pointingNodes[cV])
        {
            if (fromNode[node].count(cU))
            {
                toMerge.push({cU, find(node)});
            }
        }

        for (const auto &[key, value] : fromComp[cV])
        {
            if (value > 0 && fromComp[key][cU] > 0)
            {
                toMerge.push({cU, key});
            }
        }

        answer -= 1LL * nodes[cV].size() * pointingNodes[cV].size();
        for (const int &node : pointingNodes[cV])
        {
            fromNode[node].erase(fromNode[node].find(cV));
            fromComp[find(node)][cV]--;

            bool inserted = pointingNodes[cU].insert(node).second;
            if (inserted) 
            {
                answer += nodes[cU].size();
                fromNode[node].insert(cU);
                fromComp[find(node)][cU]++;
            }
        }
        
        answer += 1LL * pointingNodes[cU].size() * nodes[cV].size();
        for (const auto &[key, value] : fromComp[cV])
        {
            fromComp[cU][key] += value;
        }

        for (const int &node : nodes[cV])
        {
            nodes[cU].insert(node);
        }

        par[cV] = cU;
        // while (toMerge.size())
        // {
        //     merge(toMerge.front().first, toMerge.front().second);
        //     toMerge.pop();
        // }
    }

    void addEdge(int u, int v)
    {
        int cU = find(u);
        int cV = find(v);
        if (cU == cV) 
        {
            return;
        }

        if (fromNode[u].count(cV))
        {
            return;
        }

        if (!fromComp[cV].count(cU))
        {
            answer += nodes[cV].size();
            pointingNodes[cV].insert(u);
            fromNode[u].insert(cV);
            fromComp[cU][cV]++;
            return;
        }
        
        assert(fromComp[cU][cV] == 0);
        merge(cU, cV);
    }
};

DSU dsu;
int from[MAXM];
int to[MAXM];
void solve()
{
    dsu.build();
    for (int i = 1 ; i <= m ; ++i)
    {
        dsu.addEdge(from[i], to[i]);
        std::cout << answer << '\n';
    }
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> from[i] >> to[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

/*
14 13
10 14
3 10
14 13
1 3
3 5
3 11
12 14
14 6
11 8
2 3
7 8
9 7
1 4

5 6
4 2
1 5
2 3
2 5
3 2
3 1
*/

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 22104 KB Output is correct
2 Correct 6 ms 22108 KB Output is correct
3 Runtime error 24 ms 44624 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 22104 KB Output is correct
2 Correct 6 ms 22108 KB Output is correct
3 Runtime error 24 ms 44624 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 22104 KB Output is correct
2 Correct 6 ms 22108 KB Output is correct
3 Runtime error 24 ms 44624 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -