Submission #834440

#	Time	Username	Problem	Language	Result	Execution time	Memory
834440		algorithm16	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	5 ms	9684 KiB

joitter2

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long int llint;
llint p[100005],sz[100005],cnt[100005],r;
multiset <int> in[100005],out[100005];
set <pair<int,int> > s;
int find_par(int x) {
	if(x==p[x]) return x;
	int p1=find_par(p[x]);
	p[x]=p1;
	return p1;
}
void edge(int a,int b) {
	if(a==b) return;
	if(out[a].find(b)!=out[a].end()) return;
	in[b].insert(a);
	out[a].insert(b);
	cnt[b]+=sz[b];
	r+=sz[b];
	if(out[b].find(a)!=out[b].end()) {
		while(in[b].find(a)!=in[b].end()) {
			in[b].erase(in[b].find(a));
			cnt[b]-=sz[b];
			r-=sz[b];
		}
		while(in[a].find(b)!=in[a].end()) {
			in[a].erase(in[a].find(b));
			cnt[a]-=sz[a];
			r-=sz[a];
		}
		out[b].erase(a);
		out[a].erase(b);
		s.insert(make_pair(a,b));
	}
}
void f(int x,int y) {
	x=find_par(x);
	y=find_par(y);
	if(x==y) return;
	//cout << " " << r << "\n";
	if(in[x].size()+out[x].size()<in[y].size()+out[y].size()) swap(x,y);
	for(multiset <int>::iterator it=in[y].begin();it!=in[y].end();) {
		int a=(*it);
		out[a].erase(y);
		edge(a,x);
		it=in[y].erase(it);
	}
	for(multiset <int>::iterator it=out[y].begin();it!=out[y].end();) {
		int a=(*it);
		in[a].erase(y);
		edge(x,a);
		it=out[y].erase(it);
	}
	//cout << " " << r << " " << cnt[x]+cnt[y] << "\n";
	r-=sz[x]*(sz[x]-1);
	r-=sz[y]*(sz[y]-1);
	r-=cnt[x];
	r-=cnt[y];
	sz[x]+=sz[y];
	r+=sz[x]*(sz[x]-1);
	cnt[x]=in[x].size()*sz[x];
	//cout << "  " << r << "\n";
	r+=cnt[x];
	in[y].clear();
	out[y].clear();
	p[y]=x;
	//cout << " " << r << "\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	llint n,m,e=0;
	cin >> n >> m;
	for(int i=0;i<n;i++) {
		p[i]=i;
		sz[i]=1;
	}
	for(int i=0;i<m;i++) {
		int x,y;
		cin >> x >> y;
		x=find_par(x-1);
		y=find_par(y-1);
		edge(x,y);
		while(!s.empty()) {
			int a=(*s.begin()).first,b=(*s.begin()).second;
			s.erase(s.begin());
			f(a,b);
		}
		cout << r << "\n";
		/*for(int j=0;j<n;j++) {
			cout << find_par(j) << " ";
		}
		cout << "\n";*/
	}
	return 0;
}

/*

           __
          /\ \
         /  \ \
        / /\ \ \
       / / /\ \ \
      / / /__\_\ \
     / / /________\
     \/___________/


*/

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:76:12: warning: unused variable 'e' [-Wunused-variable]
   76 |  llint n,m,e=0;
      |            ^

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