제출 #720063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720063		walterw	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	1060 ms	107692 KiB

joitter2

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

ll sz[100005], par[100005];

int findset(int i) {
    return (par[i] == i? i : par[i] = findset(par[i]));
}

ll ans = 0;
set<ll> in[100005], out[100005];
queue<pair<ll, ll>> q;

void join(int a, int b) {
    a = findset(a);
    b = findset(b);

    if (a == b) return;

    if (sz[a] > sz[b]) swap(a, b);
    ans -= (sz[a] * in[a].size() + sz[b] * in[b].size());

    par[a] = b;
    sz[b] += sz[a];

    for (auto a : in[a]) {
        in[b].insert(a);
        out[findset(a)].insert(b);

        if (findset(a) != b && out[b].find(findset(a)) != out[b].end()) {
            q.push({a, b});
        }
    }

    for (auto cur : out[a]) {
        out[b].insert(cur);
        if (findset(cur) != b && out[findset(cur)].find(b) != out[findset(cur)].end()) {
            q.push({cur, b});
        }
    }

    ans += sz[b] * in[b].size();
}


void add(int a, int b) {
    b = findset(b);

    if (in[b].find(a) != in[b].end() || findset(a) == b) return;

    if (out[b].find(findset(a)) != out[b].end()) {
        // join them
        q.push({a, b});
        while (!q.empty()) {
            auto [c, d] = q.front();
            q.pop();
            join(c, d);
        }
        return;
    }

    in[b].insert(a);
    out[findset(a)].insert(b);
    ans += sz[b];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m; cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        sz[i] = 1; par[i] = i;
        in[i].insert(i);
        out[i].insert(i);
    }

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

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