제출 #795947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795947		Ozy	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	7 ms	14420 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " <<  a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 100000

lli n,m,a,b,res;
lli uf[MAX+2],tam[MAX+2];
set<lli> llegan[MAX+2],salen[MAX+2],hijos[MAX+2];
queue<pll> cola;

lli sube(lli pos) {
    if (uf[pos] == pos) return pos;
    uf[pos] = sube(uf[pos]);
    return uf[pos];
}

void arista_azul(lli a, lli b) {
    llegan[b].insert(a);
    salen[a].insert(b);
    if (llegan[a].count(b)) cola.push({a,b});
}

lli func(lli t) {return (t*(t-1));}

lli sz(lli a) {return (hijos[a].size() + llegan[a].size() + salen[a].size());}

void solve(lli a, lli b) {
    if (a == b) return;

    //debugsl(a);
    //debugsl(b);
    //debug(res);

    //res -= func(tam[a]);
    //res -= func(tam[b]);
    //res += func(tam[a] + tam[b]);

    res += hijos[a].size()*tam[b] + tam[a]*hijos[b].size();

    if (sz(a) < sz(b)) swap(a,b);

    tam[a] += tam[b];
    uf[b] = a;

    llegan[a].erase(b); 
    salen[b].erase(a);
    llegan[b].erase(a);
    salen[a].erase(b);

    for(auto h : hijos[b]) {
        if (hijos[a].count(h)) res -= tam[a];
        else hijos[a].insert(h);
    }
    for(auto act : llegan[b]) {
        salen[act].erase(b);
        arista_azul(act,b);
    }
    for(auto act : salen[b]) {
        llegan[act].erase(b);
        arista_azul(b,act);
    }

    debug(res);
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    // inicializa
    rep(i,1,n) {
        uf[i] = i;
        tam[i] = 1;
        hijos[i].insert(i);  //porque se inserta a si mismo
    }
    
    rep(i,1,m) {
        cin >> a >> b;

        b = sube(b);
        if(sube(a) == b || hijos[b].count(a)) {
            cout << res << "\n";   
            continue;
        }

        hijos[b].insert(a);
        res += tam[b];

        a = sube(a);
        arista_azul(a,b);


        while (!cola.empty()) {
            pll act = cola.front();
            cola.pop();
            solve(sube(act.first),sube(act.second));
        }
        cout << res << "\n";
    }

    return 0;
}

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