Submission #211996

#	Time	Username	Problem	Language	Result	Execution time	Memory
211996		qkxwsm	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1002 ms	99576 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 100013;

int N, M;
int dsu[MAXN], siz[MAXN];
vi edge[MAXN];
ll ans;

set<int> in[MAXN]; //vertices into the CLIQUE i.
map<int, set<int> > out[MAXN]; //edges between cliques. out[x][y] stores for all x -> y,what are the actual vertices?

void merge(int u, int v);

int get(int u)
{
    return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
void addedge(int u, int v)
{
    // cerr << "addedge " << u << ' ' << v << endl;
    int x = get(u), y = get(v);
    if (x == y || in[y].find(u) != in[y].end())
    {
        //do nothing.
    }
    else if (SZ(out[x][y]) > 0 || SZ(out[y][x]) == 0)
    {
        //maybe x -> y has an edge already?
        out[x][y].insert(u);
        ans += siz[y];
        in[y].insert(u);
    }
    else
    {
        for (auto a : out[y][x])
        {
            // cerr << "in " << x << " erase " << a << endl;
            in[x].erase(a);
            ans -= siz[x];
        }
        // cerr << "ans = " << ans << endl;
        out[y].erase(x);
        //y -> x has an edge already.
        merge(x, y);
    }
}
void merge(int u, int v)
{
    u = get(u);
    v = get(v);
    if (u == v) return;
    // if (get(u) == get(v)) return;
    // assert(get(u) == u);
    // assert(get(v) == v);
    for (int x : out[u][v])
    {
        in[v].erase(x);
        ans -= siz[v];
    }
    for (int x : out[v][u])
    {
        in[u].erase(x);
        ans -= siz[u];
    }
    out[u][v].clear();
    out[v][u].clear();
    // cerr << "merge " << u << ' ' << v << endl;
    ans += 2ll * siz[u] * siz[v];
    // cerr << "ans = " << ans << endl;
    //now the actual merging part.
    //x -> both: do nothing
    //x -> one: connect it to the other.
    //x -> u and v -> x: MERGE AGAIN.
    if (SZ(out[u]) + SZ(in[u]) < SZ(out[v]) + SZ(in[v]))
    {
        swap(u, v);
    }
    // cerr << "merging " << u << ' ' << v << endl;
    set<int> merges;
    //this takes care of all edges stemming out of the connected component of v.
    for (auto it = out[v].begin(); it != out[v].end();)
    {
        if ((it -> se).empty())
        {
            it = out[v].erase(it);
            continue;
        }
        int cc = it -> fi;
        // if (cc == u)
        // assert(cc != u);
        // cerr << v << " -> " << cc << endl;
        // cerr << v << " -> " << cc << endl;
        if (SZ(out[cc][u]) > 0) //cc is the connected component that this is connected to.
        {
            //merge.
            //disconnect everything from that cc.
            for (auto a : it -> se)
            {
                in[cc].erase(a);
                ans -= siz[cc];
            }
            //disconnected everything in that cc from u.
            for (auto a : out[cc][u])
            {
                in[u].erase(a);
                ans -= siz[u];
            }
            out[cc].erase(u);
            it = out[v].erase(it);
            merges.insert(cc);
        }
        else
        {
            for (auto a : it -> se)
            {
                out[u][it -> fi].insert(a);
            }
            it++;
        }
    }
    out[v].clear();
    int cnt = 0, cnt1 = 0;
    for (int w : in[v])
    {
        // cerr << "w = " << w << endl;
        int cc = get(w);
        out[cc].erase(v);
        if (merges.find(cc) != merges.end() || SZ(out[u][cc]) > 0)
        {
            // cerr << "pity " << w << endl;
            for (int z : out[u][cc])
            {
                ans -= siz[cc];
                in[cc].erase(z);
            }
            // cerr << "ans " << ans << endl;
            out[u].erase(cc);
            merges.insert(cc);
            ans -= siz[v];
            // cerr << "ans " << ans << endl;
            continue;
        }
        else if (in[u].find(w) != in[u].end())
        {
            cnt++;
        }
        else
        {
            in[u].insert(w);
            out[cc][u].insert(w);
            ans += siz[u];
            cnt1++;
        }
    }
    // cerr << SZ(in[u]) << ' ' << cnt << ' ' << cnt1 << endl;
    ans += (SZ(in[u]) - cnt - cnt1) * siz[v];
    in[v].clear();
    dsu[v] = u;
    siz[u] += siz[v];
    siz[v] = 0;
    for (auto a : merges)
    {
        merge(a, u);
    }
    return;
}

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    // freopen("test.out", "w", stdout);
    cin >> N >> M;
    FOR(i, 0, N)
    {
        dsu[i] = i;
        siz[i] = 1;
    }
    //store edges of the form clique -> node. they are actually reverses of the actual edges.
    //also, store clique -> clique edges.
    FOR(i, 0, M)
    {
        int u, v;
        cin >> u >> v; u--; v--;
        addedge(u, v);
        cout << ans << '\n';
        //check if u has an edge to anything in v.
    }
    return 0;
}

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