Submission #682033

#	Time	Username	Problem	Language	Result	Execution time	Memory
682033		ParsaS	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1988 ms	106496 KiB

joitter2

// In the name of God
//-MILY-
#pragma GCC optimize("O2", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define fi firsst
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
const int N = 1e5 + 5;
int n, m;
set<pair<int, int> > st;
vector<int> Q;
int par[N], sz[N];
ll ans;
vector<int> ver[N];
set<int> out[N], in[N], OUT[N];
map<int, int> cnt[N];

int get(int v) {
    return par[v] == v ? v : par[v] = get(par[v]);
}

inline void unite(int x, int y) {
    int dx = out[x].size() + in[x].size();
    int dy = out[y].size() + in[y].size();
    if (sz[x] > sz[y])
        swap(x, y);

    par[x] = y;
    unordered_set<int> vin, vout;
    unordered_map<int, int> tmp;
    ll delta = 2LL * sz[x] * sz[y];
    delta -= 1LL * cnt[x][y] * sz[y] + 1LL * cnt[y][x] * sz[x];

    int inBoth = 0;

    for (auto v : in[x]) {
        if (get(v) == y) {
            continue;
        }
        if (!in[y].count(v)) {
            cnt[get(v)][y]++;
            delta += sz[y];
        }
        else
            inBoth++;

        OUT[v].erase(x);
        OUT[v].insert(y);
        vin.insert(get(v));
        
    }
    delta += 1LL * sz[x] * (in[y].size() - inBoth - cnt[x][y]);
    for (auto v : out[x]) {
        vout.insert(get(v));
    }
    for (auto v : vin) {
        if (st.count(mp(v, x)) && st.count(mp(y, v))) {
            Q.pb(v);
        }
        if (st.count(mp(v, x)))
            st.erase(mp(v, x));
        st.insert(mp(v, y));
    }
    for (auto v : vout) {
        if (st.count(mp(x, v)) && st.count(mp(v, y))) {
            Q.pb(v);
        }
        cnt[y][v] += cnt[x][v];
        if (st.count(mp(x, v)))
            st.erase(mp(x, v));
        st.insert(mp(y, v));
    }


    for (auto v : in[x])
        if (get(v) != y)
            in[y].insert(v);
    for (auto v : out[x])
        if (get(v) != y)
            out[y].insert(v);

    ans += delta;


    for (auto v : ver[x])
        if (in[y].count(v))
            in[y].erase(v);
    if (ver[x].size() > ver[y].size())
        ver[x].swap(ver[y]);
    for (auto v : ver[x])
        ver[y].pb(v);

    sz[y] += sz[x];
}

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
        ver[i].pb(i);
    }


    while (m--) {
        int v, u; cin >> v >> u;
        int y = get(u), x = get(v);
        if (OUT[v].count(y)) {
            cout << ans << '\n';
            continue;
        }
        if (st.count(mp(y, x))) {
            Q.pb(y);
        }
        else {
            ans += sz[y];
            OUT[v].insert(y);
            st.insert(mp(x, y));
            in[y].insert(v);
            out[x].insert(u);
            cnt[x][y]++;
        }
        while (!Q.empty()) {
            int y = Q.back();
            Q.pop_back();
            if (get(x) == get(y))
                continue;
            unite(x, y);
            x = get(x);
        }
        cout << ans << '\n';
    }
}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void unite(int, int)':
joitter2.cpp:26:9: warning: unused variable 'dx' [-Wunused-variable]
   26 |     int dx = out[x].size() + in[x].size();
      |         ^~
joitter2.cpp:27:9: warning: unused variable 'dy' [-Wunused-variable]
   27 |     int dy = out[y].size() + in[y].size();
      |         ^~

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