Submission #1263291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263291		hahahoang132	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	430 ms	130832 KiB

joitter2

//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e6 + 5;
const ll inf = LLONG_MAX/5;
const ll mod = 998244353;
#define bit(x,y) ((x >> y) & 1LL)

set<ll> a[N];
set<pair<ll,ll>> b[N];
ll p[N],sz[N];
ll ans = 0;
queue<pair<ll,ll>> mg;
ll fp(ll x)
{
    if(p[x] == 0) return x;
    else
    {
        p[x] = fp(p[x]);
        return p[x];
    }
}
ll check(ll x, ll y)
{
    x = fp(x);
    y = fp(y);
    if(x == y) return 0;
    if((*b[x].lower_bound({y,0})).first == y && (*b[y].lower_bound({x,0})).first == x) return 1;
    else return 0;
}
void hop(ll x, ll y)
{
    x = fp(x);
    y = fp(y);
    if(x == y) return;
    if(a[y].size() + b[y].size() > a[x].size() + b[x].size()) swap(x,y);
    ans -= sz[x] * (sz[x] - 1) + (a[x].size()) * sz[x];
    ans -= sz[y] * (sz[y] - 1) + (a[y].size()) * sz[y];
    for(auto tmp : a[y])
    {
        if(fp(tmp) == x) continue;
        ll pt = fp(tmp);
        a[x].insert(tmp);
        b[pt].erase({y,tmp});
        b[pt].insert({x,tmp});
        if(check(x,pt)) mg.push({x,pt});
    }
    for(auto tmp : b[y])
    {
        ll t1 = tmp.first;
        ll t2 = tmp.second;
        if(t1 == x)
        {
            a[x].erase(t2);
            continue;
        }
        b[x].insert({t1,t2});
        if(check(x,t1)) mg.push({x,t1});
    }
    a[y].clear();
    b[y].clear();
    sz[x] += sz[y];
    p[y] = x;
    ans += sz[x] * (sz[x] - 1) + (a[x].size()) * sz[x];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;
    cin >> n >> m;
    ll i,j;
    for(i = 1;i <= n;i++)
    {
        p[i] = 0;
        sz[i] = 1;
    }
    for(i = 1;i <= m;i++)
    {
        ll x,y;
        cin >> x >> y;
        if(fp(x) == fp(y))
        {
            cout << ans << "\n";
        }else
        {
            b[fp(x)].insert({fp(y),x});
            ans -= sz[fp(y)] * (a[fp(y)].size());
            a[fp(y)].insert(x);
            ans += sz[fp(y)] * (a[fp(y)].size());
            if(check(x,y)) mg.push({x,y});
            while(!mg.empty())
            {
                hop(mg.front().first,mg.front().second);
                mg.pop();
            }
            cout << ans << "\n";
        }
    }
}

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