Submission #246492

#	Time	Username	Problem	Language	Result	Execution time	Memory
246492		egekabas	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	9 ms	7424 KiB

joitter2

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
ll ans = 0;
ll sq = 500;
ll n, m;
ll prt[100009];
ll sz[100009];
ll bigid[100009];
ll curbig = 1;
ll bigin[509][100009];
ll bigout[509][100009];
ll totin[100009];
vector<ll> in[100009];
vector<ll> out[100009];
bitset<100009> tmp;
vector<ll> normal[100009];
ll findprt(ll x){
    if(prt[x] == x) return x;
    return prt[x] = findprt(prt[x]);
}
void makebig(ll x){
    bigid[x] = curbig++;
    for(auto u : in[x]){
        bigin[bigid[x]][findprt(u)]++;
        if(findprt(u) != x)
            totin[x]++;
    }
    for(auto u : out[x])
        bigout[bigid[x]][findprt(u)]++;
}
ll calc(ll x){
    if(bigid[x]) return totin[x]*sz[x];
    ll cur = 0;
    for(auto u : in[x])
        if(findprt(u) != x) cur += sz[x];
    return cur;
}
void merge(ll x, ll y){
    x = findprt(x);
    y = findprt(y);
    if(x == y) return;
    if(bigid[y] || (!bigid[x] && in[y].size()+out[y].size() > in[x].size()+out[x].size()))
        swap(x, y);
    
    if(bigid[x]){
        if(bigin[bigid[x]][y] == 0 || bigout[bigid[x]][y] == 0)
            return;
    }
    else{
        ll goin = 0;
        ll goout = 0;
        for(auto u : in[y])
            if(findprt(u) == x)++goin;
        for(auto u : out[y])
            if(findprt(u) == x)++goout;
        if(goin == 0 || goout == 0)
            return;
    }
    ans -= calc(x)+calc(y);
    vector<ll> mergelater;  
    if(bigid[x] && bigid[y]){
        totin[x] -= bigin[bigid[x]][y];
        prt[y] = x;
        for(int i = 1; i <= n; ++i){
            if(findprt(i) != i || i == x) continue;
            totin[x] += bigin[bigid[y]][i];
            bigout[bigid[x]][i] += bigout[bigid[y]][i];
            bigin[bigid[x]][i] += bigin[bigid[y]][i];
            if(bigout[bigid[x]][i] && bigin[bigid[x]][i])
                mergelater.pb(i);
        }
        ans -= sz[x]*(sz[x]-1)+sz[y]*(sz[y]-1);
        sz[x] += sz[y];
        ans += sz[x]*(sz[x]-1);
    }
    else if(bigid[x]){
        totin[x] -= bigin[bigid[x]][y];
        prt[y] = x;
        for(auto u : in[y]){
            bigin[bigid[x]][findprt(u)]++;
            if(findprt(u) != x)
                totin[x]++;
            if(findprt(u) != x && bigout[bigid[x]][u])
                mergelater.pb(u);
        }
        for(auto u : out[y]){
            bigout[bigid[x]][findprt(u)]++;
            if(findprt(u) != x && bigin[bigid[x]][u])
                mergelater.pb(u);
        }
        ans -= sz[x]*(sz[x]-1)+sz[y]*(sz[y]-1);
        sz[x] += sz[y];
        ans += sz[x]*(sz[x]-1);
    }
    else{
        prt[y] = x;
        for(auto u : in[y])
            if(findprt(u) != x) in[x].pb(u);
        for(auto u : out[y])
            if(findprt(u) != x) out[x].pb(u);
        ans -= sz[x]*(sz[x]-1)+sz[y]*(sz[y]-1);
        sz[x] += sz[y];
        ans += sz[x]*(sz[x]-1);
        for(auto u : in[x])
            tmp[findprt(u)] = 1;
        for(auto u : out[x])
            if(tmp[findprt(u)] && findprt(u) != x)
                mergelater.pb(u);
        for(auto u : in[x])
            tmp[findprt(u)] = 0;
    }
    for(ll i = 1; i < curbig; ++i){
        bigin[i][x] += bigin[i][y];
        bigin[i][y] = 0;
        bigout[i][x] += bigout[i][y];
        bigout[i][y] = 0; 
    }
    if(!bigid[x] && ll(in[x].size()+out[x].size()) > sq)
        makebig(x);
    ans += calc(x);
    for(auto u : mergelater)
        merge(x, u);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    //freopen("in.txt", "r", stdin);                                                                                             
    //freopen("out.txt", "w", stdout);

    cin >> n >> m;
    for(ll i = 1; i <= n; ++i){
        sz[i] = 1;
        prt[i] = i;
    }
    while(m--){
        ll x, y;
        cin >> x >> y;
        ll dont = (findprt(x) == findprt(y));
        for(auto u : normal[x])
            if(findprt(u) == findprt(y))
                dont = 1;
        if(dont){
            cout << ans << '\n';
            continue;
        }
        normal[x].pb(y);
        x = findprt(x);
        y = findprt(y);
        if(x != y) ans += sz[y];
        if(bigid[x])
            bigout[bigid[x]][y]++;
        else
            out[x].pb(y);
        if(bigid[y]){
            bigin[bigid[y]][x]++;
            totin[y]++;
        }
        else
            in[y].pb(x);
        merge(x, y);
        cout << ans << '\n';
    }
}

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