Submission #874218

#	Time	Username	Problem	Language	Result	Execution time	Memory
874218		406	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	8 ms	30844 KiB

joitter2

//besmellah
#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ar = array<int, 2>;

const int N = 3e5 + 5;
const long long INF = 1ll << 60;

int ans = 0;

namespace dsu {
        int dpr[N];
        set<array<int, 2>> in[N], out[N];
        //sz[v] => sum of in[v].second
        void init() {
                memset(dpr, -1, sizeof dpr);
        }
        int gpr(int x) {
                return dpr[x] < 0 ? x : dpr[x] = gpr(dpr[x]);
        }
        bool ise(int v, int u) {//u <- v
                auto it = in[u].lower_bound({v, -1});
                return it != in[u].end() && (*it)[0] == v;
        }
        void merge(int u, int v) {
                u = gpr(u), v = gpr(v);
                if (u == v) return;
                if (in[u].size() + out[u].size() > in[v].size() + out[v].size()) swap(u, v);

                auto it = in[u].lower_bound({v, -1});
                while (it != in[u].end() && (*it)[0] == v) {
                        ans -= -dpr[v];
                        out[v].erase({u, (*it)[1]});
                        in[u].erase(it);
                        it = in[u].lower_bound({v, -1});
                }
                it = in[v].lower_bound({u, -1});
                while (it != in[v].end() && (*it)[0] == u) {
                        ans -= -dpr[u];
                        out[u].erase({v, (*it)[1]});
                        in[v].erase(it);
                        it = in[v].lower_bound({u, -1});
                }
                it = out[u].lower_bound({v, -1});
                assert(it == out[u].end() || (*it)[0] != v);
                it = out[v].lower_bound({u, -1});
                assert(it == out[v].end() || (*it)[0] != u);
                ans += dpr[u] * dpr[v] * 2ll;

                vector<int> q;

                int only_v = in[v].size();
                for (auto [rt, x]: in[u]) only_v -= in[v].count({rt, x});
                ans += -dpr[u] * only_v;
                for (auto [rt, x]: in[u]) if (!in[v].count({rt, x}))
                        ans += -dpr[v];

                for (auto [rt, x]: in[u]) {
                        in[v].insert({rt, x});
                        out[rt].erase({u, x});
                        out[rt].insert({v, x});
                        if (ise(v, rt) && ise(rt, v)) q.push_back(rt);
                }
                for (auto [rt, x]: out[u]) {
                        out[v].insert({rt, x});
                        in[rt].erase({u, x});
                        in[rt].insert({v, x});
                        if (ise(v, rt) && ise(rt, v)) q.push_back(rt);
                }
                in[u].clear(), out[u].clear();

                dpr[v] += dpr[u];
                dpr[u] = v;
                for (auto x: q) merge(x, v);
        }
        void E(int u, int v) {
                int tu = u;
                u = gpr(u), v = gpr(v);
                if (u == v || in[v].count({u, tu})) return;
                in[v].insert({u, tu});
                out[u].insert({v, tu});
                ans += -dpr[v];
                if (ise(u, v) && ise(v, u)) {
                        merge(u, v);
                }
        }
}

int n, m;

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        dsu::init();
        cin >> n >> m;
        FOR(i, 0, m) {
                int u, v;
                cin >> u >> v;
                --u, --v;
                dsu::E(u, v);
                cout << ans << '\n';
        }
        return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83