Submission #533188

#	Time	Username	Problem	Language	Result	Execution time	Memory
533188		balbit	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	17 / 100	419 ms	72388 KiB

joitter2

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

#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#ifdef BALBIT
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 1e5+5;
int par[maxn];
int sz[maxn];
set<int> here[maxn];
set<int> ing[maxn];
set<int> outg[maxn]; // which sets point out of me
set<int> intopt[maxn]; // which individual points point into me
int find(int x) {
    return x == par[x]? x : par[x] = find(par[x]);
}

int re = 0;

queue<pii> tomerge;

void mrg(int A, int B){
    A = find(A); B= find(B);
    if (A == B) return;
    bug(A,B);
    re -= SZ(intopt[B]) * sz[B] + SZ(intopt[A]) * sz[A];
    re -= (sz[B]) * (sz[B]-1) + (sz[A] * (sz[A]-1));
    if (SZ(here[B]) < SZ(intopt[A])) {
        for (int x : here[B]) {
            if (intopt[A].count(x)) intopt[A].erase(x);
        }
    }else{
        set<int> nset;
        for( int x : intopt[A]) {
            if (!here[B].count(x)) {
                nset.insert(x);
            }
        }
        intopt[A].swap(nset);
    }

    if (SZ(here[A]) < SZ(intopt[B])) {
        for (int x : here[A]) {
            if (intopt[B].count(x)) intopt[B].erase(x);
        }
    }else{
        set<int> nset;
        for( int x : intopt[B]) {
            if (!here[A].count(x)) {
                nset.insert(x);
            }
        }
        intopt[B].swap(nset);
    }

    if (SZ(intopt[A]) + SZ(here[A]) + SZ(outg[A]) + SZ(ing[A]) > SZ(intopt[B]) + SZ(here[B]) + SZ(outg[B]) + SZ(ing[B])) {
        swap(A,B); //swapped = 1;
    }
    // a into b

    for (int x : intopt[A]) {
        intopt[B].insert(x);
    }

    for (int x : here[A]) {
        here[B].insert(x);
    }

    for (int x : outg[A]) {
        if (x != B) {
            outg[B].insert(x);
            ing[x].erase(A); ing[x].insert(B);
            if (ing[B].count(x)) {
                bug("bruh? ", A, B, x);
                tomerge.push({B,x});
            }
        }
    }

    for (int x : ing[A]) {
        if (x != B) {
            ing[B].insert(x);
            outg[x].erase(A); outg[x].insert(B);
            if (outg[B].count(x)) {
                bug("yo? ", A, B, x);
                tomerge.push({B,x});
            }
        }
    }

    outg[B].erase(A);
    ing[B].erase(A);

    sz[B] += sz[A];
    par[A] = B;
    bug(SZ(intopt[B]));
    re += SZ(intopt[B]) * sz[B];
    re += (sz[B] * (sz[B]-1));
    bug(re);
}

void add(int a, int b) { // edge from A to B
    int A = find(a), B = find(b);
    if (A == B) return;
    if (intopt[B].count(a)) return;

    if (outg[B].count(A)) {
        // merge sequence!
        bool swapped = 0;
        tomerge.push({A,B});
        while (!tomerge.empty()) {
            mrg(tomerge.front().f, tomerge.front().s);
            tomerge.pop();
        }
    }else{
        ing[B].insert(A);
        outg[A].insert(B);
        intopt[B].insert(a);

        re += sz[B];
    }

}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);
    int n,m; cin>>n>>m;
    REP(i,n) {
        par[i] = i; sz[i] = 1; here[i].insert(i);
    }

    REP(i,m) {
        int a,b; cin>>a>>b; --a; --b;
        add(a,b);
        cout<<re<<endl;
    }
}

Compilation message (stderr)

joitter2.cpp: In function 'void add(int, int)':
joitter2.cpp:130:14: warning: unused variable 'swapped' [-Wunused-variable]
  130 |         bool swapped = 0;
      |              ^~~~~~~

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