Submission #985279

#	Time	Username	Problem	Language	Result	Execution time	Memory
985279		tfgs	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	4 ms	15860 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
#define int int64_t

#ifdef LOCAL
#include "algo/debug.h"
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-bg(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-bg(a); }

int n, m;
queue<array<int, 2>> to_merge;
const int max_n = 1e5;
set<int> child[max_n], g[max_n], gr[max_n];
int sz[max_n], par[max_n], ans = 0;

int find(int u) {
    return par[u] == u ? u : par[u]=find(par[u]);
}
int dsu_size(int U) {
    return child[U].size() + g[U].size() + gr[U].size();
}

void weak_connect(int U, int V) {
    g[U].insert(V); gr[V].insert(U);
    if (g[V].count(U)) {
        to_merge.push({U, V});
    }
}
void onion(int U, int V) {
    if (U == V) return;
    if (dsu_size(U) < dsu_size(V)) swap(U, V);
    ans += sz[U]*child[V].size() + sz[V]*child[U].size();
    par[V] = U;
    sz[U] += sz[V];
    for (auto c : child[V]) {
        if (child[V].count(c)) ans -= sz[U];
        else child[U].insert(c);
    }

    g[U].erase(V); g[V].erase(U);
    gr[U].erase(V); gr[V].erase(U);
    for (auto u : g[V]) {
        gr[V].erase(u);
        weak_connect(u, V);
    }
    for (auto u : gr[V]) {
        g[u].erase(V);
        weak_connect(V, u);
    }
}
void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) par[i] = i, sz[i]=1;
    while (m--) {
        int u, v; cin >> u >> v; u--; v--;
        int U = find(u), V = find(v);
        if (U == V) continue;
        if (!child[V].count(u)) {
            child[V].insert(u);
            ans += sz[V];

            weak_connect(U, V);
            while (to_merge.size()) {
                onion(find(to_merge.back()[0]), find(to_merge.back()[1]));
                to_merge.pop();
            }
        }
        cout << ans << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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