제출 #573376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573376		hollwo_pelw	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	1345 ms	78352 KiB

joitter2

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
 
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
 
void Hollwo_Pelw();
 
signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
 
const int N = 1e5 + 5;
 
int n, m, par[N];
long long ans, sz[N];
set<int> adj[N], rev[N], fol[N];
queue<pair<int, int>> to_merge;
 
void weakedge(int u, int v){
	adj[u].insert(v);
	rev[v].insert(u);
	// if now strong 
	if (adj[v].count(u))
		to_merge.push({u, v});
}
 
int find(int u){
	return par[u] = (par[u] == u ? u : find(par[u]));
}
 
int dsize(int u){
	return fol[u].size() + rev[u].size() + adj[u].size();
}
 
void merge(int u, int v){
	if ((u = find(u)) == (v = find(v))) return ;
	if (dsize(u) < dsize(v)) swap(u, v);
	ans += sz[u] * fol[v].size()
		 + sz[v] * fol[u].size();
	par[v] = u;
	sz[u] += sz[v];
	
	for (auto f : fol[v]){
		if (fol[u].count(f))
			ans -= sz[u];
		else 
			fol[u].insert(f);
	}
	
	adj[u].erase(v), rev[v].erase(u);
	adj[v].erase(u), rev[u].erase(v);
	
	for (auto f : adj[v]){
		rev[f].erase(v);
		weakedge(u, f);
	}
	for (auto f : rev[v]){
		adj[f].erase(u);
		weakedge(f, u);
	}
}
 
void Hollwo_Pelw(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		par[i] = i;
		sz[i] = 1;
		fol[i].insert(i);
	}
	for (int u, v; m --; ){
		cin >> u >> v;
		int pu = find(u), pv = find(v);
		if (pu != pv && !fol[pv].count(u)){
			fol[pv].insert(u);
			ans += sz[pv];
			weakedge(pu, pv);
			while(!to_merge.empty()){
				auto[uu, vv] = to_merge.front();
				to_merge.pop();
				merge(uu, vv);
			}
		}
		cout << ans << "\n";
	}
}

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