제출 #918888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
918888		Tuanlinh123	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	1342 ms	89332 KiB

joitter2

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=100005;
set <pll> out[maxn];
ll ans, pa[maxn], sz[maxn];
set <ll> in[maxn], comin[maxn], comout[maxn];

ll Find(ll i)
{
    if (pa[i]!=i)
        pa[i]=Find(pa[i]);
    return pa[i];
}

void addedge(ll a, ll b)
{
    ll Pa=Find(a), Pb=Find(b);
    if (Pa==Pb) return;
    if (comin[Pa].find(Pb)!=comin[Pa].end())
    {
        if (sz[Pa]<sz[Pb]) swap(Pa, Pb);
        vector <pll> upd;
        for (pll i:out[Pb])
        {
            in[i.se].erase(i.fi), ans-=sz[i.se];
            if (i.se!=Pa) upd.pb(i);
        }
        ans+=(ll)in[Pa].size()*sz[Pb];
        for (ll i:comin[Pb])
        {
            comin[Pa].insert(i);
            comout[i].erase(Pb);
            comout[i].insert(Pa);
        }
        for (ll i:comout[Pb])
        {
            comout[Pa].insert(i);
            comin[i].erase(Pb);
            comin[i].insert(Pa);
        }
        for (ll i:in[Pb])
        {
            ll f=Find(i); out[f].erase(mp(i, Pb));
            if (f==Pa) ans-=sz[Pb];
            else if (in[Pa].find(i)==in[Pa].end())
                upd.pb(mp(i, Pa)), ans-=sz[Pb];
            else ans-=sz[Pb];
        }
        ans-=sz[Pa]*(sz[Pa]-1)+sz[Pb]*(sz[Pb]-1);
        sz[Pa]+=sz[Pb], pa[Pb]=Pa;
        ans+=sz[Pa]*(sz[Pa]-1);
        for (pll i:upd) addedge(i.fi, i.se);
    }
    else if (in[Pb].find(a)==in[Pb].end())
    {
        comin[Pb].insert(Pa), in[Pb].insert(a); 
        comout[Pa].insert(Pb), out[Pa].insert({a, Pb});
        ans+=sz[Pb];
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m; cin >> n >> m;
    for (ll i=1; i<=n; i++)
        pa[i]=i, sz[i]=1;
    for (ll i=1; i<=m; i++)
    {
        ll u, v; cin >> u >> v;
        addedge(u, v), cout << ans << "\n";
    }
}

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