Submission #227052

#	Time	Username	Problem	Language	Result	Execution time	Memory
227052		DS007	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	16 ms	14464 KiB

joitter2

#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;
 
        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);
      
        par[v] = u;
        if (in_grp[v].size() > in_grp[u].size())
            swap(in_grp[v], in_grp[u]);
        if (in_ver[v].size() > in_ver[u].size())
            swap(in_ver[v], in_ver[u]);
 
        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);
        out_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++);
        for (auto itr = in_ver[u].lower_bound({u, 0}); itr != in_ver[u].end() && itr->first == u;)
            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++);
        }
 
        for (auto &i : in_grp[v]) {
            if (in_grp[i].count(u))
                merge(u, i);
        }
 
        for (auto &i : out_grp[v]) {
            if (in_grp[u].count(i))
                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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83