Submission #313143

#	Time	Username	Problem	Language	Result	Execution time	Memory
313143		vipghn2003	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	737 ms	40884 KiB

joitter2

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;

const int N=1e5+5;
int n,m,p[N],sz[N];
set<int>in[N];
set<pii>out[N];
long long res;

int Find(int x)
{
    if(x==p[x]) return x;
    return p[x]=Find(p[x]);
}

void Union(int u, int v)
{
    int x=Find(u);
    int y=Find(v);
    if(x==y) return;
    auto it=out[y].lower_bound(mp(x,0));
    if(it!=out[y].end()&&(*it).fi==x)
    {
        if(in[x].size()+out[x].size()<in[y].size()+out[y].size()) swap(x,y);
        vector<pii>vo;
        for(auto&i:out[y])
        {
            res-=sz[i.fi];
            in[i.fi].erase(i.se);
            if(i.fi!=x) vo.push_back(i);
        }
        out[y].clear();
        res+=1ll*sz[y]*(2*sz[x]+in[x].size()-in[y].size());
        vector<int>vi;
        for(auto&i:in[y])
        {
            int j=Find(i);
            out[j].erase(mp(y,i));
            if(j!=x) vi.push_back(i);
        }
        in[y].clear();
        p[y]=x;
        sz[x]+=sz[y];
        for(auto&i:vi) Union(i,x);
        for(auto&i:vo) Union(i.se,i.fi);
    }
    else if(!in[y].count(u))
    {
        res+=sz[y];
        in[y].insert(u);
        out[x].insert(mp(y,u));
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        sz[i]=1;
    }
    while(m--)
    {
        int u,v;
        cin>>u>>v;
        Union(u,v);
        cout<<res<<'\n';
    }
}

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