답안 #945188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
945188	2024-03-13T13:44:38 Z	michified	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	컴파일 오류	0 ms	0 KB

joitter2

#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline bool isin(ll a, unordered_set<ll>& s) {
    return s.find(a) != s.end();
}

int main() {
    ll n, m, i, a, b, ans = 0;
    cin >> n >> m;
    vector<vector<ll>> queries(m, vector<ll>(2));
    for (i = 0; i < m; i++) cin >> queries[i][0] >> queries[i][1];
    vector<set<ll>> A(n + 1), AB(n + 1), f(n + 1), rf(n + 1);
    vector<ll> root(n + 1);
    queue<pair<ll, ll>> tomerge;
    ll cura, curb;
    for (i = 0; i <= n; i++) {
        A[i].insert(i);
        AB[i].insert(i);
        root[i] = i;
    }

    for (i = 0; i < m; i++) {
        a = queries[i][0];
        b = queries[i][1];
        f[root[a]].insert(root[b]);
        rf[root[b]].insert(root[a]);
        if (not isin(a, AB[root[b]])) {
            AB[root[b]].insert(a);
            ans += A[root[b]].size();
        }
        if (isin(root[a], f[root[b]]) and root[a] != root[b]) tomerge.push(make_pair(root[a], root[b]));
        while (not tomerge.empty()) {
            cura = root[tomerge.front().first];
            curb = root[tomerge.front().second];
            tomerge.pop();
            if (cura == curb) continue;
            ans -= A[cura].size() * (AB[cura].size() - 1);
            ans -= A[curb].size() * (AB[curb].size() - 1);
            if (AB[cura].size() < AB[curb].size()) swap(cura, curb);
            for (ll elem : AB[curb]) AB[cura].insert(elem);
            for (ll elem : A[curb]) A[cura].insert(elem);
            ans += A[cura].size() * (AB[cura].size() - 1);
            f[cura].erase(curb);
            for (ll elem : f[curb]) {
                if (elem == cura) {
                    rf[cura].erase(curb);
                    continue;
                }
                f[cura].insert(elem);
                rf[elem].insert(cura);
                rf[elem].erase(curb);
                if (isin(cura, f[elem])) tomerge.push(make_pair(elem, cura));
            }
            for (ll elem : rf[curb]) {
                if (elem == cura) continue;
                f[elem].insert(cura);
                f[elem].erase(curb);
                rf[cura].insert(elem);
                if (isin(elem, f[cura])) tomerge.push(make_pair(elem, cura));
            }
            for (ll elem : A[curb]) root[elem] = cura;
        }
        cout << ans << endl;
    }
    return 0;
}


/*
8 14
1 2
2 1
3 4
4 3
5 6
6 5
7 8
8 7
1 5
1 3
6 3
4 8
7 6
3 2
*/

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:29:36: error: invalid initialization of reference of type 'std::unordered_set<long long int>&' from expression of type '__gnu_cxx::__alloc_traits<std::allocator<std::set<long long int> >, std::set<long long int> >::value_type' {aka 'std::set<long long int>'}
   29 |         if (not isin(a, AB[root[b]])) {
      |                                    ^
joitter2.cpp:5:43: note: in passing argument 2 of 'bool isin(long long int, std::unordered_set<long long int>&)'
    5 | inline bool isin(ll a, unordered_set<ll>& s) {
      |                        ~~~~~~~~~~~~~~~~~~~^
joitter2.cpp:33:37: error: invalid initialization of reference of type 'std::unordered_set<long long int>&' from expression of type '__gnu_cxx::__alloc_traits<std::allocator<std::set<long long int> >, std::set<long long int> >::value_type' {aka 'std::set<long long int>'}
   33 |         if (isin(root[a], f[root[b]]) and root[a] != root[b]) tomerge.push(make_pair(root[a], root[b]));
      |                                     ^
joitter2.cpp:5:43: note: in passing argument 2 of 'bool isin(long long int, std::unordered_set<long long int>&)'
    5 | inline bool isin(ll a, unordered_set<ll>& s) {
      |                        ~~~~~~~~~~~~~~~~~~~^
joitter2.cpp:54:39: error: invalid initialization of reference of type 'std::unordered_set<long long int>&' from expression of type '__gnu_cxx::__alloc_traits<std::allocator<std::set<long long int> >, std::set<long long int> >::value_type' {aka 'std::set<long long int>'}
   54 |                 if (isin(cura, f[elem])) tomerge.push(make_pair(elem, cura));
      |                                       ^
joitter2.cpp:5:43: note: in passing argument 2 of 'bool isin(long long int, std::unordered_set<long long int>&)'
    5 | inline bool isin(ll a, unordered_set<ll>& s) {
      |                        ~~~~~~~~~~~~~~~~~~~^
joitter2.cpp:61:39: error: invalid initialization of reference of type 'std::unordered_set<long long int>&' from expression of type '__gnu_cxx::__alloc_traits<std::allocator<std::set<long long int> >, std::set<long long int> >::value_type' {aka 'std::set<long long int>'}
   61 |                 if (isin(elem, f[cura])) tomerge.push(make_pair(elem, cura));
      |                                       ^
joitter2.cpp:5:43: note: in passing argument 2 of 'bool isin(long long int, std::unordered_set<long long int>&)'
    5 | inline bool isin(ll a, unordered_set<ll>& s) {
      |                        ~~~~~~~~~~~~~~~~~~~^