oj.uz

Submission #227018

# Submission time Handle Problem Language Result Execution time Memory
227018 2020-04-25T21:28:07 Z DS007 Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 12 ms 14464 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5 + 5, M = 3e5;
set<int> in_grp[N], out_grp[N];
set<pair<int, int>> in_ver[N];
int ans = 0, n, m;

class DSU {
    int n, *par, *grp_size;

public:
    DSU(int n) {
        this->n = n;
        par = new int[n];
        grp_size = new int[n];
        iota(par, par + n, 0);
        fill(grp_size, grp_size + n, 1);
    }

    int parent(int v) {
        if (v == par[v])
            return v;
        else
            return par[v] = parent(par[v]);
    }

    void merge(int u, int v) {
        u = parent(u), v = parent(v);
        if (u == v)
            return;

        par[v] = u;
        if (in_grp[v].size() > in_grp[u].size())
            swap(in_grp[v], in_grp[u]);
        if (out_grp[v].size() > out_grp[u].size())
            swap(out_grp[v], out_grp[u]);
        if (in_ver[v].size() > in_ver[u].size())
            swap(in_ver[v], in_ver[u]);

        ans -= in_ver[v].size() * grp_size[v] + in_ver[u].size() * grp_size[u] + grp_size[v] * (grp_size[v] - 1) + grp_size[u] * (grp_size[u] - 1);

        in_grp[u].insert(in_grp[v].begin(), in_grp[v].end());
        out_grp[u].insert(out_grp[v].begin(), out_grp[v].end());
        in_ver[u].insert(in_ver[v].begin(), in_ver[v].end());
        in_grp[u].erase(v);
        grp_size[u] += grp_size[v];
        for (auto itr = in_ver[u].lower_bound({v, 0}); itr != in_ver[u].end() && itr->first == v;)
            in_ver[u].erase(itr++);

        ans += in_ver[u].size() * grp_size[u] + grp_size[u] * (grp_size[u] - 1);

        for (auto &i : out_grp[v]) {
            in_grp[i].erase(v);
            in_grp[i].insert(u);

            for (auto itr = in_ver[i].lower_bound({v, 0}); itr != in_ver[i].end() && itr->first == v;)
                in_ver[i].insert({u, itr->second}), in_ver[i].erase(itr++);

            if (in_grp[u].count(i))
                merge(u, i);
        }

        for (auto &i : in_grp[v]) {
            if (out_grp[i].count(u))
                merge(u, i);
        }
    }

    void add(int u, int v) {
        int pu = parent(u), pv = parent(v);
        if (pu == pv || in_ver[pv].count({pu, u}))
            return;

        if (in_grp[pu].count(pv)) {
            merge(pu, pv);
            return;
        }

        out_grp[pu].insert(pv);
        in_grp[pv].insert(pu);
        in_ver[pv].insert({pu, u});
        ans += grp_size[pv];
    }
};

void solveTestCase() {
    cin >> n >> m;
    DSU dsu(n + 1);

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase();
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -