oj.uz

답안 #550293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
550293 2022-04-17T19:56:26 Z Antekb 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 6 ms 9684 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int r[N];
using ll = long long;
ll ans=0;
bool czy[N];
int ile=0;
set<int> S[N], co[N];
int find(int i){
	if(i==r[i])return i;
	return r[i]=find(r[i]);
}
void Union(int a,int b){
	if(a==b)return;
	if(S[a].size()+co[a].size()>S[b].size()+co[b].size())swap(a, b);
	ans-=S[a].size()*1ll*co[a].size();
	ans-=S[b].size()*1ll*co[b].size();
	for(int i:S[a])if(co[b].find(i)!=co[b].end() && !czy[i])czy[i]=1, ile++;
	for(int i:co[a])if(S[b].find(i)!=S[b].end() && !czy[i])czy[i]=1, ile++;
	for(int i:S[a])S[b].insert(i);
	for(int i:co[a])co[b].insert(i);
	ans+=S[b].size()*1ll*co[b].size();
	r[a]=b;
}
int main(){
	int n, q;
	cin>>n>>q;
	for(int i=1; i<=n; i++)r[i]=i, co[i].insert(i);
	while(q--){
		int u, v;
		cin>>u>>v;
		int vv=v;
		v=find(v);
		if(S[v].find(u)==S[v].end()){
			//cout<<"a";
			S[v].insert(u);
			ans+=co[v].size();
			if(v==find(u) && !czy[u])czy[u]=1, ile++;
		}
		if(S[find(u)].find(vv)!=S[find(u)].end()){
			//cout<<"b";
			Union(find(u), v);
		}
		cout<<ans-ile<<"\n";
	}
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -