제출 #771767

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

joitter2

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;

const int N=1e5+7;
int n,m,a[N];
ll ans,sz[N];
vector<int>st[N];
set<pair<int,int>>v[N];
vector<int>vec[N],cev[N];

void upd(int i,int x){
	for(auto u:vec[i]){
		v[a[u]].erase(mk(a[i],i));
		if(a[u]==x || a[u]==a[i])continue;
		v[a[u]].insert(mk(x,i));
	}
	for(auto u:cev[i]){
		v[a[i]].erase(mk(a[u],u));
		if(a[u]==x || a[u]==a[i])continue;
		v[x].insert(mk(a[u],u));
	}
	a[i]=x;
}

void merge(int x,int y){
	ans-=sz[x]*v[x].size();
	ans-=sz[y]*v[y].size();
	ans-=sz[x]*(sz[x]-1);
	ans-=sz[y]*(sz[y]-1);

	if(st[x].size()<st[y].size())swap(x,y);
	for(auto i:st[y]){
		upd(i,x);
		st[x].pb(i);
	}
	sz[x]+=sz[y];
	ans+=sz[x]*(sz[x]-1);
	ans+=sz[x]*v[x].size();
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		a[i]=i;
		sz[i]=1;
		st[i].pb(i);
	}
	int u,V;
	while(m--){
		cin>>u>>V;
		vec[u].pb(V);
		cev[V].pb(u);
		int x=a[u],y=a[V];
		if(x==y){
			cout<<ans<<endl;
			continue;
		}
		if(!v[y].count(mk(x,u)))ans+=1ll*(sz[y]);
		v[y].insert(mk(x,u));

		auto it=v[x].lower_bound(mk(y,0));
		if(it!=v[x].end() && it->F==y)merge(x,y);
		
		cout<<ans<<endl;
	}
}

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