Submission #1175202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175202		nrg_studio	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	11 ms	20544 KiB

joitter2

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

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int MAX_N = 1e5;
set<int> in[MAX_N], out[MAX_N], comp[MAX_N];
ll par[MAX_N], sz[MAX_N];
ll ans = 0;
queue<pair<int,int>> todo;

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

void add(int x, int y, bool a) {
    if (out[x].count(y)) {return;}

    out[x].insert(y);
    in[y].insert(x);

    if (a) {ans += sz[y];}
    
    if (out[y].count(x)) {todo.push({x,y});}
}

int tot_sz(int x) {return comp[x].size()+in[x].size()+out[x].size();}

void merge(int a, int b) {
    a = get(a); b = get(b);
    if (a==b) {return;}

    ans -= comp[a].size()*sz[a]-sz[a];
    ans -= comp[b].size()*sz[b]-sz[b];

    if (tot_sz(a)<tot_sz(b)) {
        swap(a,b);
    }

    in[a].erase(b); out[a].erase(b);
    in[b].erase(a); out[b].erase(a);

    for (int x : out[b]) {
        in[x].erase(b);
        add(a,x,true);
    }
    for (int x : in[b]) {
        out[x].erase(b);
        add(x,a,false);
    }

    for (int x : comp[b]) {comp[a].insert(x);}
    
    sz[a] += sz[b];
    ans += comp[a].size()*sz[a]-sz[a];
    par[b] = a;
}


int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    F0R(i,MAX_N) {
        par[i] = i;
        sz[i] = 1;
        comp[i].insert(i);
    }
    int n, m; cin >> n >> m;
    while (m--) {
        int a, b; cin >> a >> b;
        a--; b--;

        
        a = get(a); b = get(b);
        comp[b].insert(a);
        add(a,b,true);

        while (todo.size()) {
            merge(get(todo.front().first),get(todo.front().second));
            todo.pop();
        }
        cout << ans << '\n';
    }

    /*
    clique: yay
    join two w/ dsu if bidirectional edge

    maintain in/out set for each component
    answer for comp is |in|*|comp|+|comp|choose2
    equals |{in union comp}|*|comp size| - |comp size| holy
    
    if two comps are connected then join them Ok
    maintain num in for each comp
    */
}

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