oj.uz

Submission #927745

# Submission time Handle Problem Language Result Execution time Memory
927745 2024-02-15T09:47:24 Z vjudge1 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 5 ms 15912 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 100005
#define fi first
#define se second

typedef pair<int, int> ii;

set<int> adj[N], radj[N], st[N];
int pr[N], siz[N], n, m, res = 0;
queue<ii> q;

int find(int u){
	if (u == pr[u]) return u;
	return pr[u] = find(pr[u]);
}

void bl(int a, int b){
	adj[a].insert(b);
	radj[b].insert(a);
	if (adj[b].count(a)){
		q.push({a, b});
	}
}

int getsiz(int a){
	return st[a].size() + adj[a].size() + radj[a].size();
}

void unin(int a, int b){
	if (a == b) return;
	res += siz[a] * st[b].size() + siz[b] * st[a].size();
	if (getsiz(a) < getsiz(b)) swap(a, b);
	pr[b] = a;
	siz[a] += siz[b];
	for (auto x : st[b]){
		if (st[a].count(x)) res -= siz[a];
		else st[a].insert(x);
	}
	adj[a].erase(b);
	radj[a].erase(b);
	adj[b].erase(a);
	radj[b].erase(a);
	for (auto x : adj[b]){
		radj[x].erase(b);
		bl(a, x);
	}
	for (auto x : radj[b]){
		adj[x].erase(b);
		bl(x, a);
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
    	siz[i] = 1;
    	pr[i] = i;
    	st[i].insert(i);
    }

    while (m--){
    	int a, b;
    	cin >> a >> b;
    	b = find(b);
    	if (find(a) != b && !st[b].count(a)){
    		st[b].insert(a);
    		res += siz[b];
    	 	a = find(a);
    	 	bl(a, b);
    	 	while (!q.empty()){
    	 		a = q.front().fi;
    	 		b = q.front().se;
    	 		q.pop();
    	 		unin(a, b);
    	 	}
    	}	
    	cout << res << "\n";
    }

    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 4 ms 15708 KB Output is correct
3 Correct 4 ms 15912 KB Output is correct
4 Correct 5 ms 15708 KB Output is correct
5 Correct 3 ms 15704 KB Output is correct
6 Correct 4 ms 15708 KB Output is correct
7 Incorrect 4 ms 15792 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 4 ms 15708 KB Output is correct
3 Correct 4 ms 15912 KB Output is correct
4 Correct 5 ms 15708 KB Output is correct
5 Correct 3 ms 15704 KB Output is correct
6 Correct 4 ms 15708 KB Output is correct
7 Incorrect 4 ms 15792 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 4 ms 15708 KB Output is correct
3 Correct 4 ms 15912 KB Output is correct
4 Correct 5 ms 15708 KB Output is correct
5 Correct 3 ms 15704 KB Output is correct
6 Correct 4 ms 15708 KB Output is correct
7 Incorrect 4 ms 15792 KB Output isn't correct
8 Halted 0 ms 0 KB -