제출 #1257161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257161		denislav	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	0 / 100	8 ms	14404 KiB

joitter2

# include <iostream>
# include <vector>
# include <set>
# include <map>
using namespace std;

const int MAX=3e5+11;

int n,m;
set<int> vert_group[MAX];
set<pair<int,int>> group_group;

long long ans=0;
long long sat[MAX];
long long sz[MAX];
int par[MAX];

void init()
{
    for(int i=1;i<=n;i++)
    {
        sat[i]=0;
        sz[i]=1;
        par[i]=i;
    }
}

long long val(int x)
{
    return sz[x]*(sz[x]-1)+sat[x]*sz[x];
}

int root(int u)
{
    if(u==par[u]) return u;
    else return par[u]=root(par[u]);
}

void unite(int u, int v)
{
    ans-=val(u);
    ans-=val(v);

    //if(sz[u]<sz[v]) swap(u,v);
    vector<int> toRem;
    for(int x: vert_group[u]) if(root(x)==v) toRem.push_back(x);
    for(int x: toRem) vert_group[u].erase(x);
    for(int x: vert_group[v]) if(root(x)!=u) vert_group[u].insert(x);
    for(int x: vert_group[u]) group_group.insert({root(x),u});
    sat[u]=vert_group[u].size();
    sz[u]+=sz[v];
    par[v]=u;
    ans+=val(u);

    //cout<<"sat:"<<vert_group[u].size()<<"\n";
    //for(int x: vert_group[u]) cout<<x<<" ";
    //cout<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;
    init();
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        int ru=root(u),rv=root(v);

        if(ru==rv)
        {
            cout<<ans<<"\n";
            continue;
        }
        if(vert_group[rv].find(u)!=vert_group[rv].end())
        {
            cout<<ans<<"\n";
            continue;
        }

        if(group_group.find({rv,ru})==group_group.end())
        {
            group_group.insert({ru,rv});
            vert_group[rv].insert(u);
            ans+=sz[rv];
            sat[rv]++;
            //cout<<"add sat:"<<ru<<"->"<<rv<<"\n";
        }
        else
        {
            unite(ru,rv);
            //cout<<"merge groups:"<<ru<<" "<<rv<<"\n";
        }

        cout<<ans<<"\n";
    }

    return 0;
}

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