제출 #423595

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

joitter2

#include <iostream>
#include <set>
#include <vector>
using namespace std;

/*
x -> y <=> x follows y

Social exchange event
Choose x & y such that x -> y
Chooze z such that z =/= x, x -/-> z, y <-> z
Set x -> z

Let A and B be friends, iff A <-> B

Repeatedly, if x follows y, x begins to follow a friend of y

1    2    3    4    5    6
1 -> 2    3    4    5    6
1 -> 2 -> 3    4    5    6
1 -> 2 <> 3    4    5    6
1 -> 2 <> 3 <> 4    5    6


Build DSU component of *friend* networks. Use small-to-large to get rid of edges.
*/

int main()
{
    int N, M;
    cin >> N >> M;

    long long current_res = 0;

    set<int> node_edges[N+1]; //simple edges

    vector<int> node_col(N+1);
    vector<int> col_list[N+1];
    set<int> col_inedges[N+1];

    for(int i = 1; i <= N; i++)
    {
        node_col[i] = i;
        col_list[i].push_back(i);
    }

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

        //Basic update
        node_edges[A].insert(B);


        current_res -= (long long)col_list[ node_col[B] ].size() * (long long)col_inedges[ node_col[B] ].size();

        col_inedges[ node_col[B] ].insert(A);

        current_res += (long long)col_list[ node_col[B] ].size() * (long long)col_inedges[ node_col[B] ].size();


        //Check if friend components of A and B should be merged
        if(node_edges[B].find(A) != node_edges[B].end() && node_col[A] != node_col[B])
        {
            int U = node_col[A];
            int V = node_col[B];

            current_res -= (long long)col_list[U].size() * (long long)col_inedges[U].size();
            current_res -= (long long)col_list[V].size() * (long long)col_inedges[V].size();

            current_res -= (long long)(col_list[U].size()) * (long long)(col_list[U].size() - 1);
            current_res -= (long long)(col_list[V].size()) * (long long)(col_list[V].size() - 1);

            if(col_list[U].size() < col_list[V].size())
                swap(U, V);

            for(int v: col_list[V])
            {
                col_inedges[U].erase(v);
                col_list[U].push_back(v);
                node_col[v] = U;
            }
            for(int e: col_inedges[V])
            {
                if(node_col[e] != U)
                    col_inedges[U].insert(e);
            }

            current_res += (long long)col_list[U].size() * (long long)col_inedges[U].size();
            current_res += (long long)(col_list[U].size()) * (long long)(col_list[U].size() - 1);
        }

        cout << current_res << '\n';
    }
}

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