제출 #939376

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

joitter2

#include<bits/stdc++.h>
using namespace std;
#define int long long
set<pair<int,int> > A[200000];
set<int> B[200000];
int ojc[200000],wiel[200000];
int wynik=0;
void rozpatrz(int x,int y);
int find_u(int x)
{
    if(ojc[x]==x)
        return x;
    else return ojc[x]=find_u(ojc[x]);
}
void union_f(int x,int y)
{
    x=find_u(x);
    y=find_u(y);
    if(wiel[x]>wiel[y])
        swap(x,y);
    for(int i=0;i<2;i++)
    {
        while(true)
        {
            auto it=A[x].lower_bound({y,-1});
            if(it==A[x].end())
                break;
            pair<int,int> para=*it;
            if(para.first>y)
                break;
            A[x].erase(para);
            B[para.first].erase(para.second);
            wynik-=wiel[y];
        }
        swap(x,y);
    }
    wynik+=wiel[x]*wiel[y]*2;
    vector<pair<int,int> > pomoc;
    for(auto i:A[x])
        pomoc.push_back({i.second,i.first});
    for(auto i : A[x])
    {
        B[i.first].erase(i.second);
        wynik-=wiel[i.first];
    }
    wynik-=wiel[x]*B[x].size();
    wynik+=wiel[x]*B[y].size();
    for(auto i:B[x])
        A[find_u(i)].erase({x,i});
    for(auto i:B[x])
        pomoc.push_back({i,x});
    wiel[y]+=wiel[x];
    ojc[x]=y;
    A[x].clear();
    B[x].clear();
    for(auto i:pomoc)
        rozpatrz(i.first,i.second);
}
void rozpatrz(int x,int y)
{
    if(find_u(x)==find_u(y))
        return;
    y=find_u(y);
    auto it=A[y].lower_bound({find_u(x),-1});
    if(it!=A[y].end())
    {
        pair<int,int> para=*it;
        if(para.first==find_u(x))
        {
            union_f(x,y);
            return;
        }
    }
    if(B[y].find(x)!=B[y].end())
        return;
    B[y].insert(x);
    A[find_u(x)].insert({y,x});
    wynik+=wiel[y];
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        ojc[i]=i,wiel[i]=1;
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        rozpatrz(x,y);
        cout<<wynik<<"\n";
    }
}

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