oj.uz

답안 #942211

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942211 2024-03-10T11:06:04 Z michified 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline ll combs(ll a) {
    return (a - 1) * a;
}

class UnionFind {
public:
    vector<ll> root, rank, group;
    vector<unordered_set<ll>> dependencies;
    queue<ll> todel;
    UnionFind(ll n) {
        root.resize(n);
        rank.resize(n);
        group.resize(n);
        dependencies.resize(n);
        for (ll i = 0; i < n; i++) {
            root[i] = i;
            rank[i] = 1;
            group[i] = 1;
        }
    }

    ll find(ll a) {
        if (root[a] == a) return a;
        return root[a] = find(root[a]);
    }

    unordered_set<ll>& sUnion(unordered_set<ll>& a, unordered_set<ll>& b, ll one, ll two) {
        ll rootone = find(one), roottwo = find(two);
        if (a.size() > b.size()) {
            for (ll elem : b) a.insert(elem);
            for (ll elem : a) {
                if (find(elem) == rootone or find(elem) == roottwo) todel.push(elem);
            }
            while (not todel.empty()) {
                a.erase(todel.front());
                todel.pop();
            }
            return a;
        }
        for (ll elem : a) b.insert(elem);
        for (ll elem : b) {
            if (find(elem) == roottwo or find(elem) == rootone) todel.push(elem);
        }
        while (not todel.empty()) {
            b.erase(todel.front());
            todel.pop();
        }
        return b;
    }

    void join(ll a, ll b){
        ll roota = find(a), rootb = find(b);
        if (roota != rootb) {
            if (rank[roota] < rank[rootb]) {
                group[rootb] += group[roota];
                dependencies[rootb] = sUnion(dependencies[roota], dependencies[rootb], a, b);
                root[roota] = rootb;
            } else if (rank[rootb] < rank[roota]) {
                group[roota] += group[rootb];
                dependencies[roota] = sUnion(dependencies[roota], dependencies[rootb], a, b);
                root[rootb] = roota;
            } else {
                group[rootb] += group[roota];
                dependencies[rootb] = sUnion(dependencies[roota], dependencies[rootb], a, b);
                root[roota] = rootb;
                rank[rootb]++;
            }
        }
    }

    inline bool connected(ll a, ll b) {
        return find(a) == find(b);
    }

    inline ll getg(ll a) {
        return group[find(a)];
    }

    inline ll getd(ll a) {
        return dependencies[find(a)].size();
    }

    inline void updd(ll a, ll val) {
        if (find(val) != find(a)) dependencies[find(a)].insert(val);
    }
};

int main() {
    ll n, m, i, a, b, ans = 0;
    queue<ll> todel;
    cin >> n >> m;
    vector<unordered_set<ll>> isfollowing(n + 1);
    UnionFind uf(n + 1);
    vector<vector<ll>> queries(m, vector<ll>(2));
    for (i = 0; i < m; i++) cin >> queries[i][0] >> queries[i][1];

    for (i = 0; i < m; i++) {
        a = queries[i][0];
        b = queries[i][1];

        if (isfollowing[b].find(a) == isfollowing[b].end()) {
            ans -= uf.getd(b) * uf.getg(b);
            uf.updd(b, a);
            ans += uf.getd(b) * uf.getg(b);
        } else if (not uf.connected(a,b)) {
            ans -= combs(uf.getg(a));
            ans -= combs(uf.getg(b));
            ans -= uf.getd(a) * uf.getg(a);
            ans -= uf.getd(b) * uf.getg(b);
            uf.join(a, b);
            ans += combs(uf.getg(a));
            ans += uf.getd(a) * uf.getg(a);
        }
        isfollowing[a].insert(b);

        cout << ans << endl;
    }
    return 0;
}


/*
4 6
1 2
2 3
3 2
2 1
4 1
4 3
*/

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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