oj.uz

Submission #573371

# Submission time Handle Problem Language Result Execution time Memory
573371 2022-06-06T13:05:11 Z hollwo_pelw Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 9 ms 14420 KB 
#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 : 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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 7 ms 14300 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14304 KB Output is correct
5 Incorrect 8 ms 14416 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 7 ms 14300 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14304 KB Output is correct
5 Incorrect 8 ms 14416 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 7 ms 14300 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14304 KB Output is correct
5 Incorrect 8 ms 14416 KB Output isn't correct
6 Halted 0 ms 0 KB -