Submission #768423

#	Time	Username	Problem	Language	Result	Execution time	Memory
768423		smax	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1510 ms	106948 KiB

joitter2

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

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define DEBUG(...) 6
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}

const int MAXN = 1e5 + 5;

int par[MAXN], sz[MAXN];
long long ret = 0;
set<int> adj[MAXN], radj[MAXN], followers[MAXN];
queue<pair<int, int>> que;

void conn(int u, int v) {
    adj[u].insert(v);
    radj[v].insert(u);
    if (adj[v].count(u))
        que.emplace(u, v);
}

int find(int u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

int getSz(int u) {
    return int(adj[u].size() + radj[u].size() + followers[u].size());
}

void unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v)
        return;
    if (getSz(u) < getSz(v))
        swap(u, v);
    ret += sz[u] * followers[v].size() + sz[v] * followers[u].size();
    par[v] = u;
    sz[u] += sz[v];
    for (int x : followers[v]) {
        if (followers[u].count(x))
            ret -= sz[u];
        else
            followers[u].insert(x);
    }
    adj[u].erase(v);
    radj[u].erase(v);
    adj[v].erase(u);
    radj[v].erase(u);
    for (int x : adj[v])
        conn(u, x);
    for (int x : radj[v])
        conn(x, u);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

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

    for (int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;

        b = find(b);
        if (find(a) != b && !followers[b].count(a)) {
            ret += sz[b];
            followers[b].insert(a);
            a = find(a);
            conn(a, b);
            while (!que.empty()) {
                auto [u, v] = que.front();
                que.pop();
                unite(u, v);
            }
        }

        cout << ret << "\n";
    }

    return 0;
}

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