oj.uz

답안 #834404

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834404 2023-08-22T14:00:24 Z algorithm16 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 5 ms 9724 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],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()) {
		out[b].erase(a);
		in[b].erase(a);
		out[a].erase(b);
		in[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;
	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);
	}
	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];
	r+=cnt[x];
	in[y].clear();
	out[y].clear();
	p[y]=x;
}
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

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

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9696 KB Output is correct
2 Correct 4 ms 9724 KB Output is correct
3 Incorrect 4 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9696 KB Output is correct
2 Correct 4 ms 9724 KB Output is correct
3 Incorrect 4 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9696 KB Output is correct
2 Correct 4 ms 9724 KB Output is correct
3 Incorrect 4 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -