제출 #484234

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

joitter2

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

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

    out_edge[u].erase(v);
    out_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);
    }

    for(int i: in_edge[v])
    {
        out_edge[i].erase(v);
        out_edge[i].insert(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];

        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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83