Submission #1073113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073113		underwaterkillerwhale	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	2 ms	16988 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) (int)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;

struct Edge {
    int u, v, prio;
    bool operator < (const Edge &other) const {
        return prio > other.prio || (prio == other.prio && u < other.u) || (prio == other.prio && u == other.u && v < other.v);
    }
};

int n, m;
vector<int> cc;
map<pii, int> dEc;
set<Edge> pq;
set<pii> inS[N];///fs: cpn cua no
ll res = 0;

void Insert (pii cur) {
    pii cur2 = cur;
    if (cur2.fs > cur2.se) swap(cur2.fs, cur2.se);
    if (pq.find({cur2.fs, cur2.se, 1}) != pq.end()) {
        pq.erase(pq.find({cur2.fs, cur2.se, 1}));
    }
    pq.insert({cur2.fs, cur2.se, dEc[cur2] + dEc[MP(cur2.se, cur2.fs)]});
}

void Erase (pii cur) {
    pii cur2 = cur;
    if (cur2.fs > cur2.se) swap(cur2.fs, cur2.se);
    pq.erase(pq.find({cur2.fs, cur2.se, 1}));
}
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] ? u : Find(lab[u]);
    }

    void Join (int u, int v) {
        int uu = Find(u), vv = Find(v);
        if (uu == vv) return ;
        if (inS[vv].find(MP(uu, u)) == inS[vv].end()) res += sz[vv];
        dEc[{uu, vv}] = 1;
        inS[vv].insert({uu, u});
        Insert(MP(uu, vv));
        return ;
    }

    void noi (int u, int v) {
        pq.erase(pq.find({u, v, 2}));
//        cout << u <<" "<<v<<": \n";
//        iter (&id, pq) {
//            cout << id.u<<","<<id.v<<","<<id.prio <<" ";
//        }
//        cout<<"\n";
        if (SZ(inS[u]) < SZ(inS[v])) swap(u, v);
        ///delete old edge
        res -= sz[u] * (sz[u] - 1) + sz[v] * (sz[v] - 1);
        ///delete cross-edge
        auto it = inS[u].lower_bound({v, 0});
        while (1) {
            if (it == inS[u].end() || it->fs != v) break;
            res -= sz[v];
            it = inS[u].erase(it);
        }
        it = inS[v].lower_bound({u, 0});
        while (1) {
            if (it == inS[v].end() || it->fs != u) break;
            res -= sz[u];
            it = inS[v].erase(it);
        }
        ///add all edge
        res += (sz[u] + sz[v]) * (sz[u] + sz[v] - 1);
        ///add weak edge
        res += SZ(inS[v]) * sz[u] + SZ(inS[u]) * sz[v];
        ///remove incident
        iter (&id, inS[v]) {
            if (inS[u].find(id) != inS[u].end()) res -= sz[v] + sz[u];
        }
        ///updating pq
        iter (&id, inS[v]) {
            dEc[{id.fs, u}] = 1;
            inS[u].insert(id);
            Erase(MP(id.fs, v));
            Insert(MP(id.fs, u));
        }

        set<pii> ().swap(inS[v]);
        lab[v] = u;
        sz[u] += sz[v];
    }

    void simulate () {
        while (!pq.empty()) {
            if (pq.begin()->prio == 1) break;
            else noi(pq.begin()->u, pq.begin()->v);
        }
    }

}DSU;

void solution () {
    cin >> n >> m;
    DSU.init(n);
    rep (i, 1, m) {
        int u, v;
        cin >> u >> v;
        DSU.Join(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: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83