oj.uz

답안 #933881

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933881 2024-02-26T13:00:20 Z moonrabbit2 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 5 ms 21084 KB 
#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
const ll mod=1000000007;
const int N=100005;
int n,m;
struct UF{
	int p[N]={0};
	ll ans=0,sz[N],szIn[N];
	set<int> in[N],out[N],inV[N],S[N];
	void init(){
		for(int i=1;i<=n;i++){
			sz[i]=1;
			szIn[i]=0;
			S[i].emplace(i);
		}
	}
	int Find(int u){
		if(!p[u]) return u;
		return p[u]=Find(p[u]);
	}
	void add(int u,int v){
		int Gu=Find(u),Gv=Find(v);
		if(Gu==Gv) return;
		if(in[Gu].count(Gv)){
			ans+=2*sz[Gu]*sz[Gv];
			ans-=sz[Gu]*inV[Gu].size();
			ans-=sz[Gv]*inV[Gv].size();
			//debug(ans,sz[Gu],sz[Gv],inV[Gu],inV[Gv]);
			if(in[Gu].size()+out[Gu].size()+inV[Gu].size()+S[Gu].size()<in[Gv].size()+out[Gv].size()+inV[Gv].size()+S[Gv].size()) swap(Gu,Gv);
			for(int Gw: in[Gv]){
				out[Gw].erase(Gv);
				out[Gw].emplace(Gu);
				in[Gu].emplace(Gw);
			}
			for(int Gw: out[Gv]){
				in[Gw].erase(Gv);
				in[Gw].emplace(Gu);
				out[Gu].emplace(Gw);
			}
			for(int w: inV[Gv]){
				if(!S[Gu].count(w)) inV[Gu].emplace(w);
				//else ans+=sz[Gv];
			}
			for(int w: S[Gv]){
				S[Gu].emplace(w);
				if(inV[Gu].count(w)){
					//ans+=sz[Gu];
					inV[Gu].erase(w);
				}
			}
			sz[Gu]+=sz[Gv];
			ans+=sz[Gu]*inV[Gu].size();
			//debug(ans,Gu,inV[Gu]);
			p[Gv]=Gu;
		} else if(!in[Gv].count(u)){
			ans+=sz[Gv];
			in[Gv].emplace(Gu);
			out[Gu].emplace(Gv);
			inV[Gv].emplace(u);
		}
	}
}U;
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	U.init();
	for(int u,v,i=1;i<=m;i++){
		cin>>u>>v;
		U.add(u,v);
		cout<<U.ans<<"\n";
	}
	return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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