Submission #313141

#	Time	Username	Problem	Language	Result	Execution time	Memory
313141		vipghn2003	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	17 / 100	5044 ms	44408 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 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: 0 / 83