Submission #1074783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074783		underwaterkillerwhale	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1970 ms	220752 KiB

joitter2

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 3e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 320;

int n, m;
map<pii,int> cnt, dd;
queue<pii> pq;
set<int> inS[N], outS[N], in[N];
ll numin[N];
ll res = 0;

struct Disjoin_set {
    ll lab[N], sz[N];

    void init (int n) {
        rep (i, 1, n) lab[i] = i, sz[i] = 1;
    }

    int Find (int u) {
        return u == lab[u] ? lab[u] = u : Find(lab[u]);
    }

    void add_edge (int u, int v) {
        int uu = Find(u), vv = Find(v);
        if (uu == vv) return;
//        cout << u<<" "<<v<<" "<<uu<<" "<<dd[{u, vv}]<<" hihi\n";
        if (dd[{u, vv}] == 0) {
            dd[{u, vv}] = 1;
            cnt[{uu, vv}]++;
            numin[vv]++;
            res += sz[vv];
        }
        if (inS[uu].find(vv) != inS[uu].end()) pq.push({uu, vv});
        inS[vv].insert(uu);
        outS[uu].insert(vv);
        in[vv].insert(u);
    }

    void Join (int u, int v) {
        u = Find(u), v = Find(v);
        if (u == v) return;
        if (SZ(in[u]) + SZ(outS[u]) + SZ(inS[u]) < SZ(in[v]) + SZ(outS[v]) + SZ(inS[v])) swap(u, v);
//        cout << u <<" "<<v<<" hihi\n";
        numin[u] -= cnt[{v, u}];
        numin[v] -= cnt[{u, v}];
        res -= sz[u] * (sz[u] - 1) + sz[v] * (sz[v] - 1);
        res -= sz[v] * cnt[{u, v}] + sz[u] * cnt[{v, u}];
//        cout << res<<" "<<cnt[{3, 1}]<<" "<<cnt[{1, 3}]<<"\n";
        res += (sz[u] + sz[v]) * (sz[u] + sz[v] - 1);
        res += numin[v] * sz[u] + numin[u] * sz[v];
        numin[u] += numin[v];
        iter (&id, in[v]) {
            if (Find(id) == v || Find(id) == u) continue;
            if (in[u].find(id) != in[u].end()) {
//                cout << id <<"\n";
                res -= sz[u] + sz[v];
                numin[u] --;
            }
            if (dd[{id, u}] == 0) {
                dd[{id, u}] = 1;
                cnt[{Find(id), u}]++;
            }
        }
        iter (&id, inS[v]) {
            if (id == u) continue;
            if (outS[u].find(id) != outS[u].end()) pq.push({id, u});
        }
        iter (&id, outS[v]) {
            if (id == u) continue;
            if (inS[u].find(id) != inS[u].end()) pq.push({id, u});
        }
        iter (&id, in[v]) {
            if (Find(id) == v || Find(id) == u) continue;
            dd[{id, u}] = 1;
            in[u].insert(id);
        }
        iter (&id, outS[v]) {
            if (id == u) continue;
            cnt[{u, id}] += cnt[{v, id}];
            inS[id].erase(v), inS[id].insert(u);
            outS[u].insert(id);
        }
        iter (&id, inS[v]) {
            if (id == u) continue;
            outS[id].erase(v), outS[id].insert(u);
            inS[u].insert(id);
        }
        sz[u] += sz[v];
        lab[v] = u;
    }

    void simulate () {
        while (!pq.empty()) {
            pii u = pq.front();
            pq.pop();
            Join(u.fs, u.se);
        }
    }

}DSU;

void solution () {
    cin >> n >> m;
    DSU.init(n);
    rep (i, 1, m) {
        int u, v;
        cin >> u >> v;
        DSU.add_edge(u, v);
        DSU.simulate();
        cout << res <<"\n";
    }
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
9 9 3
.........
.........
....###..
...v#....
..###....
...##...v
...##....
.........
v........
1 1
9 1
5 7
return->break
*/

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