제출 #233217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233217		medk	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	100 / 100	1737 ms	136368 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;

map<int,set<int>> in[MAXN],out[MAXN];
set<int> in2[MAXN],out2[MAXN];
vector<ll> dsu,sz,acc(MAXN);


//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]+acc[v]+sz(in2[v])+sz(out2[v])>sz[u]+acc[u]+sz(in2[u])+sz(out2[u])) swap(u,v);
    ans-=sz[u]*(sz[u]-1);
    ans-=sz[v]*(sz[v]-1);
    ans+=(sz[u]+sz[v])*(sz[u]+sz[v]-1);
    in2[u].erase(v);
    out2[u].erase(v);
    in2[v].erase(u);
    out2[v].erase(u);
    vector<int> qu;
    acc[u]-=sz(in[u][v]);
    ans+=acc[u]*sz[v];
    for(int w:in2[v])
    {
        in2[u].insert(w);
        out2[w].erase(v);
        out2[w].insert(u);
        for(int z:in[v][w])
        {
            if(!in[u][w].count(z)) {in[u][w].insert(z), ans+=sz[u], acc[u]++;}
            else ans-=sz[v];
            out[w][u].insert(z);
        }
    }
    for(int w:out2[v])
    {
        out2[u].insert(w);
        in2[w].erase(v);
        in2[w].insert(u);
        if(in2[u].count(w)) qu.pb(w);
        for(int z:out[v][w])
            out[u][w].insert(z), in[w][u].insert(z);
    }
    for(int w:in2[v])
        if(w!=u) if(out2[u].count(w)) qu.pb(w);
    ans-=sz(in[v][u])*sz[v]+sz(in[u][v])*sz[u];
    sz[u]+=sz[v];
    dsu[v]=u;
    in[u][v].clear();
    out[u][v].clear();
    in[v][u].clear();
    out[v][u].clear();
    in2[v].clear();
    in[v].clear();
    out2[v].clear();
    out[v].clear();
    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 || in[parv][paru].count(u))
        {
            cout<<ans<<'\n';
            continue;
        }
        if(in2[paru].count(parv))
        {
            connect(paru,parv);
            cout<<ans<<'\n';
            continue;
        }
        in2[parv].insert(paru);
        out2[paru].insert(parv);
        in[parv][paru].insert(u), acc[parv]++;
        out[paru][parv].insert(u);
        ans+=sz[parv];
        cout<<ans<<'\n';
    }
    return 0;
}

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