Submission #484218

#	Time	Username	Problem	Language	Result	Execution time	Memory
484218		blue	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	4 ms	9676 KiB

joitter2

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

const int maxN = 100'000;

set<int> out_edges[1+maxN];
set<int> in_edges[1+maxN];

struct ds
{
public:
    int N;
    vector<int> parent;
    vector< vector<int> > members;
    vector< set<int> > followers;

    long long answer = 0;

    ds()
    {
        ;
    }

    ds(int N_)
    {
        N = N_;
        parent = vector<int>(1+N);
        members = vector< vector<int> >(1+N);
        followers = vector< set<int> >(1+N);
        for(int i = 1; i <= N; i++)
        {
            parent[i] = i;
            members[i].push_back(i);
        }
    }

    int root(int u)
    {
        if(parent[u] == u) return u;
        else
        {
            parent[u] = root(parent[u]);
            return parent[u];
        }
    }

    long long get_score(int u)
    {
        u = root(u);
        long long s = int(members[u].size());
        long long f = int(followers[u].size());
        return s*(s-1) + s*f;
    }

    void join(int a, int b)
    {
        a = root(a);
        b = root(b);

        if(a == b) return;

        answer -= get_score(a);
        answer -= get_score(b);


        if(int(members[a].size()) < int(members[b].size())) swap(a, b);

        parent[b] = a;
        for(int m: members[b]) followers[a].erase(m);

        for(int f: followers[b])
            if(root(f) != a)
                followers[a].insert(f);

        for(int m: members[b]) members[a].push_back(m);

        members[b].clear();
        followers[b].clear();

        answer += get_score(a);

        for(int o: out_edges[a])
        {
            out_edges[b].insert(o);

            in_edges[o].erase(a);
            in_edges[o].insert(b);
        }
        for(int i: in_edges[a])
        {
            in_edges[b].insert(i);

            out_edges[i].erase(a);
            in_edges[i].insert(b);
        }

        out_edges[a].clear();
        in_edges[a].clear();
    }

    void add_follower(int b, int a)
    {
        if(root(a) == root(b)) return;
        answer -= get_score(b);
        followers[root(b)].insert(a);
        answer += get_score(b);
    }
};

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

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


    ds DSU(N);

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

        out_edges[DSU.root(A)].insert(DSU.root(B));
        in_edges[DSU.root(B)].insert(DSU.root(A));
        DSU.add_follower(B, A);

        // if(out_edges[B].find(A) != out_edges[B].end())
        //     DSU.join(A, B);
        if(out_edges[DSU.root(B)].find(DSU.root(A)) != out_edges[DSU.root(B)].end())
        {
            DSU.join(A, B);
        }

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

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