Submission #1129557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129557		PieArmy	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	7 ms	9792 KiB

joitter2

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n,m;
int par[100001];
ll siz[100001];
ll ans=0;
multiset<int>git[100001],gel[100001];

int get(int x){
	if(x==par[x])return x;
	return par[x]=get(par[x]);
}

bool unite(int x,int y){
	x=get(x);y=get(y);
	if(x==y)return false;
	while(gel[y].find(x)!=gel[y].end()){
		ans-=siz[y];
		gel[y].erase(gel[y].find(x));
	}
	while(gel[x].find(y)!=gel[x].end()){
		ans-=siz[x];
		gel[x].erase(gel[x].find(y));
	}
	if(git[x].size()<git[y].size())swap(x,y);
	ans+=ll(gel[x].size())*siz[y]+ll(gel[y].size())*siz[x]+siz[x]*siz[y]*2;
	par[y]=x;
	siz[x]+=siz[y];
	for(int a:git[y]){
		int b=get(a);
		if(b==x)continue;
		git[x].insert(b);
		auto itr=gel[b].find(y);
		if(itr!=gel[b].end()){
			gel[b].erase(itr);
			gel[b].insert(x);
		}
	}
	git[y].clear();
	if(gel[x].size()<gel[y].size())swap(gel[x],gel[y]);
	for(int a:gel[y]){
		gel[x].insert(a);
	}
	gel[y].clear();
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m;
	iota(par,par+n+1,0);
	for(int i=0;i<=n;i++){
		siz[i]=1;
	}
	while(m--){
		int a,b;cin>>a>>b;
		a=get(a);b=get(b);
		if(gel[b].find(a)!=gel[b].end()){
			cout<<ans<<endl;
			continue;
		}
		ans+=siz[b];
		git[a].insert(b);
		gel[b].insert(a);
		if(gel[a].find(b)!=gel[a].end()){
			unite(a,b);
		}
		cout<<ans<<endl;
	}
}

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