Submission #232889

#	Time	Username	Problem	Language	Result	Execution time	Memory
232889		medk	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	17 / 100	576 ms	81900 KiB

joitter2

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (long long)(u.size())
#define all(u) u.begin(),u.end()

using namespace std;

const int MAXN=1e5;
int n,m;
ll ans=0;

set<int> in[MAXN],out[MAXN],in2[MAXN],out2[MAXN];
vector<int> dsu,sz;

//in : **node** -> this group
//out : this node -> **group**
//in2 : **group** -> this group
//out2: this group -> **group**

int getp(int u)
{
    if(dsu[u]==u) return u;
    return dsu[u]=getp(dsu[u]);
}

void connect(int u, int v)
{
    u=getp(u), v=getp(v);
    if(u==v) return;
    if(sz[v]>sz[u]) swap(u,v);
    ans-=sz(in[u])*sz[u];
    ans-=sz(in[v])*sz[v];
    ans-=sz[u]*(sz[u]-1);
    ans-=sz[v]*(sz[v]-1);
    sz[u]+=sz[v];
    ans+=sz[u]*(sz[u]-1);
    in2[u].erase(v);
    out2[u].erase(v);
    vector<int> qu;
    for(int w:in2[v])
    {
        if(w==u) continue;
        in2[u].insert(w);
        out2[w].erase(v);
        out2[w].insert(u);
        if(out2[u].count(w)) qu.pb(w);
    }
    for(int w:out2[v])
    {
        int pr=getp(w);
        if(w==u || pr==u || pr==v) continue;
        out2[u].insert(w);
        in2[w].erase(v);
        in2[w].insert(u);
        if(in2[u].count(w)) qu.pb(w);
    }
    for(int w:in[v])
    {
        if(getp(w)==u) continue;
        in[u].insert(w);
        out[w].erase(v);
        out[w].insert(u);
    }
    vector<int> to_erase;
    for(int w:in[u])
    {
        if(getp(w)==v) to_erase.pb(w);
    }
    for(int x:to_erase) in[u].erase(x);
    ans+=sz[u]*sz(in[u]);
    dsu[v]=u;
    for(int q:qu) connect(u,q);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++) dsu.pb(i), sz.pb(1);
    for(int i=0;i<m;i++)
    {
        int u,v; cin>>u>>v;
        u--,v--;
        int paru=getp(u), parv=getp(v);
        if(paru==parv || out[u].count(parv))
        {
            cout<<ans<<'\n';
            continue;
        }
        if(in2[paru].count(parv))
        {
            connect(paru,parv);
            cout<<ans<<'\n';
            continue;
        }
        in2[parv].insert(paru);
        out2[paru].insert(parv);
        out[u].insert(parv);
        in[parv].insert(u);
        ans+=sz[parv];
        cout<<ans<<'\n';
    }
    return 0;
}

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