Submission #834491

# Submission time Handle Problem Language Result Execution time Memory
834491 2023-08-22T14:55:52 Z algorithm16 Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
7 ms 14420 KB
#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],in2[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);
	}
	for(multiset <int>::iterator it=in2[y].begin();it!=in2[y].end();it++) {
		in2[x].insert((*it));
		//cout << (*it) << "\n";
	}
	//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();
	in2[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;
		int x1=x-1,y1=y-1;
		x=find_par(x-1);
		y=find_par(y-1);
		if(out[x].find(y)!=out[x].end() && in2[y].find(x1)==in2[y].end()) {
			//cout << "abc\n";
			in2[y].insert(x1);
			out[x].insert(y);
			in[y].insert(x);
			r+=sz[y];
			cnt[y]+=sz[y];
		}
		else if(x!=y) in2[y].insert(x1);
		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

joitter2.cpp: In function 'int main()':
joitter2.cpp:90:14: warning: unused variable 'y1' [-Wunused-variable]
   90 |   int x1=x-1,y1=y-1;
      |              ^~
joitter2.cpp:81:12: warning: unused variable 'e' [-Wunused-variable]
   81 |  llint n,m,e=0;
      |            ^
# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Incorrect 7 ms 14420 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Incorrect 7 ms 14420 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Incorrect 7 ms 14420 KB Output isn't correct
4 Halted 0 ms 0 KB -