Submission #484242

#	Time	Username	Problem	Language	Result	Execution time	Memory
484242		blue	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1077 ms	72656 KiB

joitter2

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#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]);
}

queue< pair<int, int> > join_queue;


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

    if(u == v) return;

    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);

        if(out_edge[o].find(u) != out_edge[o].end())
            join_queue.push(make_pair(o, u));
    }

    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);

        if(in_edge[i].find(u) != in_edge[i].end())
            join_queue.push(make_pair(i, u));
    }

    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];

        // cerr << "label = " << A << ' ' << B << '\n';

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



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

            while(!join_queue.empty())
            {
                auto g = join_queue.front();
                join_queue.pop();
                join(g.first, g.second);
            }
        }

        cout << answer << '\n';



        // cerr << "\n operation done\n";
        // cerr << "labels: ";
        // for(int i = 1; i <= N; i++) cerr << label[i] << ' ';
        // cerr << '\n';
        //
        // for(int i = 1; i <= N; i++)
        // {
        //     cerr << "out edge " << i << ": ";
        //     for(int o: out_edge[i]) cerr << o << ' ';
        //     cerr << '\n';
        // }
        // cerr << "\n\n";
    }

    // for(int i = 1; i <= N; i++) cerr << label[i] << ' ';
    // cerr << '\n';
}

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