oj.uz

Submission #720056

# Submission time Handle Problem Language Result Execution time Memory
720056 2023-04-07T10:51:42 Z walterw Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 6 ms 9716 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

int sz[100005], par[100005];

int findset(int i) {
    return (par[i] == i? i : par[i] = findset(par[i]));
}

int ans = 0;
set<int> in[100005], out[100005];
queue<pair<int, int>> q;

void join(int a, int b) {
    a = findset(a);
    b = findset(b);

    if (a == b) return;

    if (sz[a] > sz[b]) swap(a, b);
    ans -= (sz[a] * in[a].size() + sz[b] * in[b].size());

    par[a] = b;
    sz[b] += sz[a];

    for (auto a : in[a]) {
        in[b].insert(a);
        out[findset(a)].insert(b);

        if (findset(a) != b && out[b].find(findset(a)) != out[b].end()) {
            q.push({a, b});
        }
    }

    for (auto cur : out[a]) {
        out[b].insert(cur);
        if (findset(cur) != b && out[findset(cur)].find(b) != out[findset(cur)].end()) {
            q.push({cur, b});
        }
    }

    ans += sz[b] * in[b].size();
}


void add(int a, int b) {
    b = findset(b);

    if (in[b].find(a) != in[b].end() || findset(a) == b) return;

    if (out[b].find(findset(a)) != out[b].end()) {
        // join them
        q.push({a, b});
        while (!q.empty()) {
            auto [c, d] = q.front();
            q.pop();
            join(c, d);
        }

        return;
    }

    in[b].insert(a);
    out[findset(a)].insert(b);
    ans += sz[b];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m; cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        sz[i] = 1; par[i] = i;
    }

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        add(a, b);
        cout << ans << "\n";
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9716 KB Output is correct
6 Incorrect 5 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9716 KB Output is correct
6 Incorrect 5 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9716 KB Output is correct
6 Incorrect 5 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -