제출 #874225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874225		406	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	920 ms	83136 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[u];
                        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[v];
                        out[u].erase({v, (*it)[1]});
                        in[v].erase(it);
                        it = in[v].lower_bound({u, -1});
                }
                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]) {
                        assert(rt != v);
                        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]) {
                        assert(rt != v);
                        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: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83