oj.uz

Submission #918885

# Submission time Handle Problem Language Result Execution time Memory
918885 2024-01-30T16:00:43 Z Tuanlinh123 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 6 ms 19804 KB 
#include<bits/stdc++.h>
#define ll int
#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);
        for (pll i:out[Pb])
        {
            if (i.se==Pa) in[Pa].erase(i.fi), ans-=sz[Pa];
            else out[Pa].insert(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);
        }
        vector <pll> upd;
        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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19800 KB Output is correct
2 Correct 5 ms 19804 KB Output is correct
3 Incorrect 6 ms 19800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19800 KB Output is correct
2 Correct 5 ms 19804 KB Output is correct
3 Incorrect 6 ms 19800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19800 KB Output is correct
2 Correct 5 ms 19804 KB Output is correct
3 Incorrect 6 ms 19800 KB Output isn't correct
4 Halted 0 ms 0 KB -