oj.uz

Submission #484236

# Submission time Handle Problem Language Result Execution time Memory
484236 2021-11-02T17:03:40 Z blue Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 8 ms 17124 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;

const int maxN = 100'000;

vector<int> label(1+maxN);
set<int> out_edge[1+maxN]; //label to label
set<int> in_edge[1+maxN];
vector<int> label_list[1+maxN];
set<int> in_count[1+maxN];

// vector<int> in_count(1+maxN, 0);

int sz(int u)
{
    return int(label_list[u].size());
}


long long answer = 0;


long long comp(int u)
{
    u = label[u];
    return (long long)(in_count[u].size()) * (long long)(label_list[u].size());
}

void insert_in(int B, int A)
{
    answer -= comp(label[B]);
    in_count[label[B]].insert(A);
    answer += comp(label[B]);
}


void join(int u, int v)
{
    u = label[u];
    v = label[v];

    assert(u != v);

    answer -= comp(u);
    answer -= comp(v);

    out_edge[u].erase(v);
    out_edge[v].erase(u);
    in_edge[u].erase(v);
    in_edge[v].erase(u);

    if(sz(u) < sz(v)) swap(u, v);

    for(int l: label_list[v])
    {
        label_list[u].push_back(l);
        label[l] = u;
    }

    for(int ic: in_count[v]) in_count[u].insert(ic);

    for(int o: out_edge[v])
    {
        out_edge[u].insert(o);
        in_edge[o].erase(v);
        in_edge[o].insert(u);
        // assert(label[o] == o);
    }

    for(int i: in_edge[v])
    {
        in_edge[u].insert(i);
        out_edge[i].erase(v);
        out_edge[i].insert(u);
        // assert(label[i] == i);
    }

    answer += comp(u);

    in_count[v].clear();
    label_list[v].clear();
    out_edge[v].clear();
    in_edge[v].clear();
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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


    for(int i = 1; i <= N; i++)
    {
        label[i] = i;
        label_list[i].push_back(i);
        in_count[i].insert(i);
    }


    for(int j = 1; j <= M; j++)
    {
        int A, B;
        cin >> A >> B;

        insert_in(B, A);

        A = label[A];
        B = label[B];

        if(A != B)
        {
            out_edge[A].insert(B);
            in_edge[B].insert(A);

            if(out_edge[B].find(A) != out_edge[B].end())
            {
                join(A, B);
            }
        }

        cout << answer << '\n';
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17100 KB Output is correct
2 Correct 8 ms 17124 KB Output is correct
3 Incorrect 7 ms 17100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17100 KB Output is correct
2 Correct 8 ms 17124 KB Output is correct
3 Incorrect 7 ms 17100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17100 KB Output is correct
2 Correct 8 ms 17124 KB Output is correct
3 Incorrect 7 ms 17100 KB Output isn't correct
4 Halted 0 ms 0 KB -