oj.uz

Submission #870662

# Submission time Handle Problem Language Result Execution time Memory
870662 2023-11-08T18:11:33 Z fatemetmhr Making Friends on Joitter is Fun (JOI20_joitter2) C++17
100 / 100
 817 ms 87456 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define sep      ' '
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const ll  mod   =  1e9   +  7;
const ll  inf   =  2e18;

ll ans;
unordered_set <int> out[maxn5], ex[maxn5], en[maxn5];
vector <int> av[maxn5], mer;
int cmp[maxn5];
queue <int> q;
bool rem[maxn5];

/*
out[a]  = rasayi ke be a (ke moalefas) yal daran;
en[a]   = moalefe hayi ke be a (ke moalefas) yal daran;
ex[a]   = moalafe hayi ke a (ke moalefas) be oona yal dare;
*/


int join(int a, int b){
	if(av[a].size() > av[b].size()) swap(a, b);
	int esh = 0;
	for(auto it = out[a].begin(); it != out[a].end(); it++){
	   	if(cmp[*it] == b) ans -= av[a].size();
	   	else if(out[b].find(*it) == out[b].end()) ans += av[b].size();
	   	if(out[b].find(*it) != out[b].end()) esh++;
	}
	
	/*/ to be removed ;.......................................................................
	for(auto it = out[b].begin(); it != out[b].end(); it++){
		if(cmp[*it] == a) ans -= av[b].size(); // done



		else if(out[a].find(*it) == out[a].end()){
			ans += av[a].size(); 
		}
	}
	// ....................................................................................... */


	ans += ll(av[a].size()) * (out[b].size() - esh); 
	ll sa = av[a].size(), sb = av[b].size();
	ans -= sa * (sa - 1);
	ans -= sb * (sb - 1);
	ans += (sa + sb) * (sa + sb - 1);
	for(auto it = en[a].begin(); it != en[a].end(); it++){
		if(ex[b].find(*it) != ex[b].end()) q.push(*it), mer.pb(*it);
	}
	for(auto it = ex[a].begin(); it != ex[a].end(); it++){
		if(en[b].find(*it) != en[b].end()) q.push(*it), mer.pb(*it);
	}
	for(auto u : mer){
	    en[a].erase(u);
	    ex[a].erase(u);
	    en[b].erase(u);
	    ex[b].erase(u);
	}
	for(auto u : av[a]){
		av[b].pb(u);
		if(out[b].find(u) != out[b].end()) ans -= sb + sa;
		out[b].erase(u);
		cmp[u] = b;
	}
	for(auto it = en[a].begin(); it != en[a].end(); it++){
		ex[*it].erase(a);
		ex[*it].insert(b);
		en[b].insert(*it);
	}
	for(auto it = ex[a].begin(); it != ex[a].end(); it++){
		en[*it].erase(a);
		en[*it].insert(b);
		ex[b].insert(*it);
	}
	for(auto it = out[a].begin(); it != out[a].end(); it++)
		if(cmp[*it] != b) out[b].insert(*it);
	av[a].cl();
	en[a].cl();
	ex[a].cl();
	out[a].cl();
	rem[a] = true;
	mer.cl();
	return b;
}

int main()
{
	//cout << setprecision(15);
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		av[i].pb(i);
		cmp[i] = i;
	}
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		if(cmp[a] != cmp[b]){
			int x = cmp[a], y = cmp[b];
			if(ex[y].find(x) != ex[y].end()){
				int now = x;
				q.push(y);		 
				while(!q.empty()){
					int v= q.front();
					q.pop();
					if(rem[v] or v == now) continue;
					now = join(now, v);
				}
			}
			else if(out[y].find(a) == out[y].end()){
				ans += av[y].size();
				ex[x].insert(y);
				en[y].insert(x);
				out[y].insert(a);
			}
		}
		cout << ans << endll;
	}
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19548 KB Output is correct
2 Correct 5 ms 19548 KB Output is correct
3 Correct 5 ms 19548 KB Output is correct
4 Correct 5 ms 19548 KB Output is correct
5 Correct 5 ms 19548 KB Output is correct
6 Correct 5 ms 19520 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 6 ms 19548 KB Output is correct
9 Correct 5 ms 19544 KB Output is correct
10 Correct 5 ms 19544 KB Output is correct
11 Correct 6 ms 19548 KB Output is correct
12 Correct 5 ms 19548 KB Output is correct
13 Correct 5 ms 19548 KB Output is correct
14 Correct 5 ms 19544 KB Output is correct
15 Correct 5 ms 19572 KB Output is correct
16 Correct 5 ms 19528 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 5 ms 19544 KB Output is correct
19 Correct 5 ms 19572 KB Output is correct
20 Correct 5 ms 19548 KB Output is correct
21 Correct 5 ms 19580 KB Output is correct
22 Correct 5 ms 19544 KB Output is correct
23 Correct 7 ms 19548 KB Output is correct
24 Correct 5 ms 19544 KB Output is correct
25 Correct 6 ms 19548 KB Output is correct
26 Correct 5 ms 19548 KB Output is correct
27 Correct 5 ms 19544 KB Output is correct
28 Correct 5 ms 19548 KB Output is correct
29 Correct 5 ms 19800 KB Output is correct
30 Correct 5 ms 19548 KB Output is correct
31 Correct 5 ms 19548 KB Output is correct
32 Correct 5 ms 19548 KB Output is correct
33 Correct 5 ms 19548 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19548 KB Output is correct
2 Correct 5 ms 19548 KB Output is correct
3 Correct 5 ms 19548 KB Output is correct
4 Correct 5 ms 19548 KB Output is correct
5 Correct 5 ms 19548 KB Output is correct
6 Correct 5 ms 19520 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 6 ms 19548 KB Output is correct
9 Correct 5 ms 19544 KB Output is correct
10 Correct 5 ms 19544 KB Output is correct
11 Correct 6 ms 19548 KB Output is correct
12 Correct 5 ms 19548 KB Output is correct
13 Correct 5 ms 19548 KB Output is correct
14 Correct 5 ms 19544 KB Output is correct
15 Correct 5 ms 19572 KB Output is correct
16 Correct 5 ms 19528 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 5 ms 19544 KB Output is correct
19 Correct 5 ms 19572 KB Output is correct
20 Correct 5 ms 19548 KB Output is correct
21 Correct 5 ms 19580 KB Output is correct
22 Correct 5 ms 19544 KB Output is correct
23 Correct 7 ms 19548 KB Output is correct
24 Correct 5 ms 19544 KB Output is correct
25 Correct 6 ms 19548 KB Output is correct
26 Correct 5 ms 19548 KB Output is correct
27 Correct 5 ms 19544 KB Output is correct
28 Correct 5 ms 19548 KB Output is correct
29 Correct 5 ms 19800 KB Output is correct
30 Correct 5 ms 19548 KB Output is correct
31 Correct 5 ms 19548 KB Output is correct
32 Correct 5 ms 19548 KB Output is correct
33 Correct 5 ms 19548 KB Output is correct
34 Correct 7 ms 19544 KB Output is correct
35 Correct 58 ms 25164 KB Output is correct
36 Correct 72 ms 27728 KB Output is correct
37 Correct 73 ms 27704 KB Output is correct
38 Correct 79 ms 27324 KB Output is correct
39 Correct 7 ms 20060 KB Output is correct
40 Correct 9 ms 20312 KB Output is correct
41 Correct 8 ms 20316 KB Output is correct
42 Correct 7 ms 20004 KB Output is correct
43 Correct 7 ms 20056 KB Output is correct
44 Correct 7 ms 20060 KB Output is correct
45 Correct 7 ms 20060 KB Output is correct
46 Correct 8 ms 20060 KB Output is correct
47 Correct 8 ms 20316 KB Output is correct
48 Correct 9 ms 20316 KB Output is correct
49 Correct 12 ms 20900 KB Output is correct
50 Correct 80 ms 27984 KB Output is correct
51 Correct 10 ms 20572 KB Output is correct
52 Correct 68 ms 26568 KB Output is correct
53 Correct 17 ms 20924 KB Output is correct
54 Correct 73 ms 27140 KB Output is correct
55 Correct 9 ms 20780 KB Output is correct
56 Correct 10 ms 20572 KB Output is correct
57 Correct 9 ms 20736 KB Output is correct
58 Correct 9 ms 20572 KB Output is correct
59 Correct 7 ms 20348 KB Output is correct
60 Correct 59 ms 25252 KB Output is correct
61 Correct 8 ms 20312 KB Output is correct
62 Correct 71 ms 27240 KB Output is correct

Subtask #3
83.0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19548 KB Output is correct
2 Correct 5 ms 19548 KB Output is correct
3 Correct 5 ms 19548 KB Output is correct
4 Correct 5 ms 19548 KB Output is correct
5 Correct 5 ms 19548 KB Output is correct
6 Correct 5 ms 19520 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 6 ms 19548 KB Output is correct
9 Correct 5 ms 19544 KB Output is correct
10 Correct 5 ms 19544 KB Output is correct
11 Correct 6 ms 19548 KB Output is correct
12 Correct 5 ms 19548 KB Output is correct
13 Correct 5 ms 19548 KB Output is correct
14 Correct 5 ms 19544 KB Output is correct
15 Correct 5 ms 19572 KB Output is correct
16 Correct 5 ms 19528 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 5 ms 19544 KB Output is correct
19 Correct 5 ms 19572 KB Output is correct
20 Correct 5 ms 19548 KB Output is correct
21 Correct 5 ms 19580 KB Output is correct
22 Correct 5 ms 19544 KB Output is correct
23 Correct 7 ms 19548 KB Output is correct
24 Correct 5 ms 19544 KB Output is correct
25 Correct 6 ms 19548 KB Output is correct
26 Correct 5 ms 19548 KB Output is correct
27 Correct 5 ms 19544 KB Output is correct
28 Correct 5 ms 19548 KB Output is correct
29 Correct 5 ms 19800 KB Output is correct
30 Correct 5 ms 19548 KB Output is correct
31 Correct 5 ms 19548 KB Output is correct
32 Correct 5 ms 19548 KB Output is correct
33 Correct 5 ms 19548 KB Output is correct
34 Correct 7 ms 19544 KB Output is correct
35 Correct 58 ms 25164 KB Output is correct
36 Correct 72 ms 27728 KB Output is correct
37 Correct 73 ms 27704 KB Output is correct
38 Correct 79 ms 27324 KB Output is correct
39 Correct 7 ms 20060 KB Output is correct
40 Correct 9 ms 20312 KB Output is correct
41 Correct 8 ms 20316 KB Output is correct
42 Correct 7 ms 20004 KB Output is correct
43 Correct 7 ms 20056 KB Output is correct
44 Correct 7 ms 20060 KB Output is correct
45 Correct 7 ms 20060 KB Output is correct
46 Correct 8 ms 20060 KB Output is correct
47 Correct 8 ms 20316 KB Output is correct
48 Correct 9 ms 20316 KB Output is correct
49 Correct 12 ms 20900 KB Output is correct
50 Correct 80 ms 27984 KB Output is correct
51 Correct 10 ms 20572 KB Output is correct
52 Correct 68 ms 26568 KB Output is correct
53 Correct 17 ms 20924 KB Output is correct
54 Correct 73 ms 27140 KB Output is correct
55 Correct 9 ms 20780 KB Output is correct
56 Correct 10 ms 20572 KB Output is correct
57 Correct 9 ms 20736 KB Output is correct
58 Correct 9 ms 20572 KB Output is correct
59 Correct 7 ms 20348 KB Output is correct
60 Correct 59 ms 25252 KB Output is correct
61 Correct 8 ms 20312 KB Output is correct
62 Correct 71 ms 27240 KB Output is correct
63 Correct 432 ms 87416 KB Output is correct
64 Correct 417 ms 87456 KB Output is correct
65 Correct 415 ms 87380 KB Output is correct
66 Correct 175 ms 51684 KB Output is correct
67 Correct 412 ms 63900 KB Output is correct
68 Correct 184 ms 51808 KB Output is correct
69 Correct 212 ms 49920 KB Output is correct
70 Correct 164 ms 51792 KB Output is correct
71 Correct 178 ms 51640 KB Output is correct
72 Correct 361 ms 57812 KB Output is correct
73 Correct 413 ms 58072 KB Output is correct
74 Correct 817 ms 73528 KB Output is correct
75 Correct 347 ms 60000 KB Output is correct
76 Correct 594 ms 69340 KB Output is correct
77 Correct 549 ms 69620 KB Output is correct
78 Correct 208 ms 61276 KB Output is correct
79 Correct 311 ms 66144 KB Output is correct
80 Correct 169 ms 53364 KB Output is correct
81 Correct 240 ms 59244 KB Output is correct
82 Correct 555 ms 80012 KB Output is correct
83 Correct 518 ms 79824 KB Output is correct
84 Correct 454 ms 80400 KB Output is correct
85 Correct 435 ms 80348 KB Output is correct
86 Correct 221 ms 61516 KB Output is correct
87 Correct 242 ms 63560 KB Output is correct
88 Correct 365 ms 57936 KB Output is correct
89 Correct 572 ms 68456 KB Output is correct