oj.uz

Submission #388090

# Submission time Handle Problem Language Result Execution time Memory
388090 2021-04-10T05:19:22 Z pure_mem Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 11 ms 14432 KB 
#include <bits/stdc++.h> 
 
#define X first
#define Y second
#define MP make_pair
#define ll long long
 
using namespace std;
 
const int MAXN = 1e5 + 12;
            
int n, m, dsu[MAXN];
set< int > children[MAXN], graph[MAXN], rgraph[MAXN];
queue< pair<int, int> > to_merge;
ll answer, sz[MAXN];

void merge(int a, int b){
	graph[a].insert(b);
	rgraph[b].insert(a);
	if(graph[b].count(a))
		to_merge.push(MP(a, b));
}

int get_pr(int v){
	if(dsu[v] == v)
		return v;
	return dsu[v] = get_pr(dsu[v]);
}

int dsu_size(int a){
	return children[a].size() + graph[a].size() + rgraph[a].size();
}

void dsu_merge(int a, int b){
	if(a == b)
		return;
	if(dsu_size(a) < dsu_size(b))
		swap(a, b);
	answer += sz[b] * children[a].size() + sz[a] * children[b].size();
	dsu[b] = a, sz[a] += sz[b];
	for(int i: children[b]){
		if(children[a].count(i)) 
			answer -= sz[a];
		else
			children[a].insert(i);
	}
	graph[a].erase(b), rgraph[a].erase(b);
	graph[b].erase(a), rgraph[b].erase(a);
	for(int i: graph[b]){
		rgraph[i].erase(b);
		merge(a, i);
	}
	for(int i: rgraph[b]){
		graph[i].erase(b);
		merge(i, a);
	}
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		sz[i] = 1, dsu[i] = i, children[i].insert(i);
	for(int a, b;m--;){
		cin >> a >> b;
		b = get_pr(b);
		if(get_pr(a) != b && !children[b].count(a)){
			children[b].insert(a);
			answer += sz[b];
			a = get_pr(a);
			merge(a, b);
			while(!to_merge.empty()){
				tie(a, b) = to_merge.front();
				to_merge.pop();
				dsu_merge(a, b);
			}	
		}
		cout << answer << "\n";	
	}
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 9 ms 14404 KB Output is correct
6 Correct 9 ms 14340 KB Output is correct
7 Incorrect 11 ms 14432 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 9 ms 14404 KB Output is correct
6 Correct 9 ms 14340 KB Output is correct
7 Incorrect 11 ms 14432 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 9 ms 14404 KB Output is correct
6 Correct 9 ms 14340 KB Output is correct
7 Incorrect 11 ms 14432 KB Output isn't correct
8 Halted 0 ms 0 KB -