oj.uz

답안 #942097

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

unordered_set<ll>& sUnion(unordered_set<ll>& a, unordered_set<ll>& b, ll one, ll two) {
    if (a.size() > b.size()) {
        for (ll elem : b) a.insert(elem);
        a.erase(one);
        a.erase(two);
        return a;
    }
    for (ll elem : a) b.insert(elem);
    b.erase(one);
    b.erase(two);
    return b;
}

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

class UnionFind {
public:
    vector<ll> root, rank, group;
    vector<unordered_set<ll>> dependencies;
    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]);
    }

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

    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) {
        dependencies[find(a)].insert(val);
    }
};

int main() {
    ll n, m, i, a, b, ans = 0;
    queue<ll> todel;
    bool found, found2;
    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.updd(b, a);
            ans += uf.getd(b);
        } else {
            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;
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:83:10: warning: unused variable 'found' [-Wunused-variable]
   83 |     bool found, found2;
      |          ^~~~~
joitter2.cpp:83:17: warning: unused variable 'found2' [-Wunused-variable]
   83 |     bool found, found2;
      |                 ^~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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