oj.uz

답안 #945158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945158 2024-03-13T12:59:51 Z michified 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 1 ms 348 KB 
#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;
    bool found;
    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<unordered_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 = tomerge.front().first;
            curb = tomerge.front().second;
            tomerge.pop();
            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);
            for (ll elem : f[curb]) {
                f[cura].insert(elem);
                rf[elem].insert(cura);
                if (isin(cura, f[elem]) and elem != cura) tomerge.push(make_pair(elem, cura));
            }
            for (ll elem : rf[curb]) {
                f[elem].insert(cura);
                f[elem].erase(curb);
                rf[cura].insert(elem);
                if (isin(elem, f[cura]) and elem != cura) tomerge.push(make_pair(elem, cura));
            }
            for (ll elem : A[curb]) root[elem] = cura;
        }
        cout << ans << endl;
    }
    return 0;
}


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

Compilation message

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

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -