oj.uz

답안 #484214

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
484214 2021-11-02T14:01:58 Z blue 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 0 ms 204 KB 
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

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

    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;

    set<int> out_edges[1+N];

    ds DSU(N);

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

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

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

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

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -