#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
set<int> adj[maxn], self[maxn], go[maxn];
int par[maxn];
map<int,int> cnt[maxn];
int get_par(int v){
return par[v] < 0 ? v : par[v] = get_par(par[v]);
}
int main(){
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
self[i].insert(i);
ll now = 0;
memset(par, -1, sizeof par);
while (m --){
int v, u;
cin >> v >> u;
int vp = get_par(v), up = get_par(u);
if (vp == up or adj[up].count(v)){
cout << now << '\n';
continue;
}
if (go[up].count(vp)){
stack<pair<int,int>> s;
s.push({v,u});
while (!s.empty()){
int v = s.top().first, u = s.top().second;
int vp = get_par(v), up = get_par(u);
s.pop();
if (vp == up)
continue;
now -= 1LL*par[vp]*(par[vp]+1) + 1LL*par[up]*(par[up]+1);
now -= -1LL*par[vp]*adj[vp].size() + -1LL*par[up]*adj[up].size();
if (par[vp] < par[up]){
swap(vp, up);
swap(v, u);
}
for (auto it : go[vp])
if (go[it].count(up))
s.push({up,it});
for (auto it : adj[vp])
if (go[up].count(get_par(it)))
s.push({get_par(it),up});
for (auto it : self[vp])
adj[up].erase(it);
for (auto it : adj[vp])
if (!self[up].count(it))
adj[up].insert(it);
for (auto it : go[vp])
go[up].insert(it);
go[up].erase(vp);
for (auto it : adj[vp]){
go[get_par(it)].erase(vp);
go[get_par(it)].insert(up);
}
go[vp].clear();
for (auto it : self[vp])
self[up].insert(it);
self[vp].clear(), adj[vp].clear();
par[up] += par[vp];
par[vp] = up;
now += 1LL*par[up]*(par[up]+1) -1LL*par[up]*adj[up].size();
}
}
else{
now += -par[up];
go[vp].insert(up);
adj[up].insert(v);
}
cout << now << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
19456 KB |
Output is correct |
2 |
Correct |
13 ms |
19584 KB |
Output is correct |
3 |
Correct |
13 ms |
19456 KB |
Output is correct |
4 |
Correct |
14 ms |
19456 KB |
Output is correct |
5 |
Correct |
14 ms |
19456 KB |
Output is correct |
6 |
Correct |
13 ms |
19456 KB |
Output is correct |
7 |
Correct |
19 ms |
19584 KB |
Output is correct |
8 |
Correct |
19 ms |
19584 KB |
Output is correct |
9 |
Correct |
19 ms |
19584 KB |
Output is correct |
10 |
Correct |
13 ms |
19456 KB |
Output is correct |
11 |
Correct |
13 ms |
19584 KB |
Output is correct |
12 |
Correct |
14 ms |
19456 KB |
Output is correct |
13 |
Correct |
13 ms |
19456 KB |
Output is correct |
14 |
Correct |
13 ms |
19456 KB |
Output is correct |
15 |
Correct |
13 ms |
19456 KB |
Output is correct |
16 |
Correct |
13 ms |
19456 KB |
Output is correct |
17 |
Correct |
14 ms |
19456 KB |
Output is correct |
18 |
Correct |
13 ms |
19456 KB |
Output is correct |
19 |
Correct |
13 ms |
19456 KB |
Output is correct |
20 |
Correct |
14 ms |
19584 KB |
Output is correct |
21 |
Correct |
19 ms |
19584 KB |
Output is correct |
22 |
Correct |
14 ms |
19584 KB |
Output is correct |
23 |
Correct |
16 ms |
19584 KB |
Output is correct |
24 |
Correct |
14 ms |
19584 KB |
Output is correct |
25 |
Correct |
18 ms |
19584 KB |
Output is correct |
26 |
Correct |
14 ms |
19584 KB |
Output is correct |
27 |
Correct |
14 ms |
19584 KB |
Output is correct |
28 |
Correct |
13 ms |
19584 KB |
Output is correct |
29 |
Correct |
13 ms |
19456 KB |
Output is correct |
30 |
Correct |
13 ms |
19456 KB |
Output is correct |
31 |
Correct |
18 ms |
19584 KB |
Output is correct |
32 |
Correct |
14 ms |
19456 KB |
Output is correct |
33 |
Correct |
18 ms |
19584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
19456 KB |
Output is correct |
2 |
Correct |
13 ms |
19584 KB |
Output is correct |
3 |
Correct |
13 ms |
19456 KB |
Output is correct |
4 |
Correct |
14 ms |
19456 KB |
Output is correct |
5 |
Correct |
14 ms |
19456 KB |
Output is correct |
6 |
Correct |
13 ms |
19456 KB |
Output is correct |
7 |
Correct |
19 ms |
19584 KB |
Output is correct |
8 |
Correct |
19 ms |
19584 KB |
Output is correct |
9 |
Correct |
19 ms |
19584 KB |
Output is correct |
10 |
Correct |
13 ms |
19456 KB |
Output is correct |
11 |
Correct |
13 ms |
19584 KB |
Output is correct |
12 |
Correct |
14 ms |
19456 KB |
Output is correct |
13 |
Correct |
13 ms |
19456 KB |
Output is correct |
14 |
Correct |
13 ms |
19456 KB |
Output is correct |
15 |
Correct |
13 ms |
19456 KB |
Output is correct |
16 |
Correct |
13 ms |
19456 KB |
Output is correct |
17 |
Correct |
14 ms |
19456 KB |
Output is correct |
18 |
Correct |
13 ms |
19456 KB |
Output is correct |
19 |
Correct |
13 ms |
19456 KB |
Output is correct |
20 |
Correct |
14 ms |
19584 KB |
Output is correct |
21 |
Correct |
19 ms |
19584 KB |
Output is correct |
22 |
Correct |
14 ms |
19584 KB |
Output is correct |
23 |
Correct |
16 ms |
19584 KB |
Output is correct |
24 |
Correct |
14 ms |
19584 KB |
Output is correct |
25 |
Correct |
18 ms |
19584 KB |
Output is correct |
26 |
Correct |
14 ms |
19584 KB |
Output is correct |
27 |
Correct |
14 ms |
19584 KB |
Output is correct |
28 |
Correct |
13 ms |
19584 KB |
Output is correct |
29 |
Correct |
13 ms |
19456 KB |
Output is correct |
30 |
Correct |
13 ms |
19456 KB |
Output is correct |
31 |
Correct |
18 ms |
19584 KB |
Output is correct |
32 |
Correct |
14 ms |
19456 KB |
Output is correct |
33 |
Correct |
18 ms |
19584 KB |
Output is correct |
34 |
Correct |
39 ms |
19712 KB |
Output is correct |
35 |
Correct |
749 ms |
24824 KB |
Output is correct |
36 |
Correct |
767 ms |
27000 KB |
Output is correct |
37 |
Correct |
765 ms |
27072 KB |
Output is correct |
38 |
Correct |
766 ms |
26824 KB |
Output is correct |
39 |
Correct |
25 ms |
19712 KB |
Output is correct |
40 |
Correct |
27 ms |
19840 KB |
Output is correct |
41 |
Correct |
28 ms |
19840 KB |
Output is correct |
42 |
Correct |
25 ms |
19712 KB |
Output is correct |
43 |
Correct |
26 ms |
19840 KB |
Output is correct |
44 |
Correct |
26 ms |
19712 KB |
Output is correct |
45 |
Correct |
25 ms |
19712 KB |
Output is correct |
46 |
Correct |
25 ms |
19712 KB |
Output is correct |
47 |
Correct |
27 ms |
19840 KB |
Output is correct |
48 |
Correct |
27 ms |
19840 KB |
Output is correct |
49 |
Correct |
47 ms |
20224 KB |
Output is correct |
50 |
Correct |
783 ms |
27128 KB |
Output is correct |
51 |
Correct |
43 ms |
19968 KB |
Output is correct |
52 |
Correct |
749 ms |
26232 KB |
Output is correct |
53 |
Correct |
46 ms |
20216 KB |
Output is correct |
54 |
Correct |
754 ms |
26444 KB |
Output is correct |
55 |
Correct |
27 ms |
20096 KB |
Output is correct |
56 |
Correct |
27 ms |
20096 KB |
Output is correct |
57 |
Correct |
28 ms |
20096 KB |
Output is correct |
58 |
Correct |
27 ms |
20088 KB |
Output is correct |
59 |
Correct |
27 ms |
19712 KB |
Output is correct |
60 |
Correct |
746 ms |
24824 KB |
Output is correct |
61 |
Correct |
29 ms |
19840 KB |
Output is correct |
62 |
Correct |
764 ms |
26892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
19456 KB |
Output is correct |
2 |
Correct |
13 ms |
19584 KB |
Output is correct |
3 |
Correct |
13 ms |
19456 KB |
Output is correct |
4 |
Correct |
14 ms |
19456 KB |
Output is correct |
5 |
Correct |
14 ms |
19456 KB |
Output is correct |
6 |
Correct |
13 ms |
19456 KB |
Output is correct |
7 |
Correct |
19 ms |
19584 KB |
Output is correct |
8 |
Correct |
19 ms |
19584 KB |
Output is correct |
9 |
Correct |
19 ms |
19584 KB |
Output is correct |
10 |
Correct |
13 ms |
19456 KB |
Output is correct |
11 |
Correct |
13 ms |
19584 KB |
Output is correct |
12 |
Correct |
14 ms |
19456 KB |
Output is correct |
13 |
Correct |
13 ms |
19456 KB |
Output is correct |
14 |
Correct |
13 ms |
19456 KB |
Output is correct |
15 |
Correct |
13 ms |
19456 KB |
Output is correct |
16 |
Correct |
13 ms |
19456 KB |
Output is correct |
17 |
Correct |
14 ms |
19456 KB |
Output is correct |
18 |
Correct |
13 ms |
19456 KB |
Output is correct |
19 |
Correct |
13 ms |
19456 KB |
Output is correct |
20 |
Correct |
14 ms |
19584 KB |
Output is correct |
21 |
Correct |
19 ms |
19584 KB |
Output is correct |
22 |
Correct |
14 ms |
19584 KB |
Output is correct |
23 |
Correct |
16 ms |
19584 KB |
Output is correct |
24 |
Correct |
14 ms |
19584 KB |
Output is correct |
25 |
Correct |
18 ms |
19584 KB |
Output is correct |
26 |
Correct |
14 ms |
19584 KB |
Output is correct |
27 |
Correct |
14 ms |
19584 KB |
Output is correct |
28 |
Correct |
13 ms |
19584 KB |
Output is correct |
29 |
Correct |
13 ms |
19456 KB |
Output is correct |
30 |
Correct |
13 ms |
19456 KB |
Output is correct |
31 |
Correct |
18 ms |
19584 KB |
Output is correct |
32 |
Correct |
14 ms |
19456 KB |
Output is correct |
33 |
Correct |
18 ms |
19584 KB |
Output is correct |
34 |
Correct |
39 ms |
19712 KB |
Output is correct |
35 |
Correct |
749 ms |
24824 KB |
Output is correct |
36 |
Correct |
767 ms |
27000 KB |
Output is correct |
37 |
Correct |
765 ms |
27072 KB |
Output is correct |
38 |
Correct |
766 ms |
26824 KB |
Output is correct |
39 |
Correct |
25 ms |
19712 KB |
Output is correct |
40 |
Correct |
27 ms |
19840 KB |
Output is correct |
41 |
Correct |
28 ms |
19840 KB |
Output is correct |
42 |
Correct |
25 ms |
19712 KB |
Output is correct |
43 |
Correct |
26 ms |
19840 KB |
Output is correct |
44 |
Correct |
26 ms |
19712 KB |
Output is correct |
45 |
Correct |
25 ms |
19712 KB |
Output is correct |
46 |
Correct |
25 ms |
19712 KB |
Output is correct |
47 |
Correct |
27 ms |
19840 KB |
Output is correct |
48 |
Correct |
27 ms |
19840 KB |
Output is correct |
49 |
Correct |
47 ms |
20224 KB |
Output is correct |
50 |
Correct |
783 ms |
27128 KB |
Output is correct |
51 |
Correct |
43 ms |
19968 KB |
Output is correct |
52 |
Correct |
749 ms |
26232 KB |
Output is correct |
53 |
Correct |
46 ms |
20216 KB |
Output is correct |
54 |
Correct |
754 ms |
26444 KB |
Output is correct |
55 |
Correct |
27 ms |
20096 KB |
Output is correct |
56 |
Correct |
27 ms |
20096 KB |
Output is correct |
57 |
Correct |
28 ms |
20096 KB |
Output is correct |
58 |
Correct |
27 ms |
20088 KB |
Output is correct |
59 |
Correct |
27 ms |
19712 KB |
Output is correct |
60 |
Correct |
746 ms |
24824 KB |
Output is correct |
61 |
Correct |
29 ms |
19840 KB |
Output is correct |
62 |
Correct |
764 ms |
26892 KB |
Output is correct |
63 |
Correct |
1014 ms |
57988 KB |
Output is correct |
64 |
Correct |
1016 ms |
57904 KB |
Output is correct |
65 |
Correct |
1012 ms |
57848 KB |
Output is correct |
66 |
Correct |
701 ms |
28664 KB |
Output is correct |
67 |
Correct |
952 ms |
33656 KB |
Output is correct |
68 |
Correct |
695 ms |
28612 KB |
Output is correct |
69 |
Correct |
936 ms |
33400 KB |
Output is correct |
70 |
Correct |
747 ms |
28584 KB |
Output is correct |
71 |
Correct |
743 ms |
28664 KB |
Output is correct |
72 |
Correct |
986 ms |
33796 KB |
Output is correct |
73 |
Correct |
1020 ms |
33552 KB |
Output is correct |
74 |
Correct |
1822 ms |
42184 KB |
Output is correct |
75 |
Correct |
1371 ms |
38096 KB |
Output is correct |
76 |
Correct |
1508 ms |
41572 KB |
Output is correct |
77 |
Correct |
1516 ms |
41720 KB |
Output is correct |
78 |
Correct |
608 ms |
34552 KB |
Output is correct |
79 |
Correct |
1168 ms |
37880 KB |
Output is correct |
80 |
Correct |
599 ms |
34552 KB |
Output is correct |
81 |
Correct |
1110 ms |
37752 KB |
Output is correct |
82 |
Correct |
1164 ms |
46712 KB |
Output is correct |
83 |
Correct |
1208 ms |
46584 KB |
Output is correct |
84 |
Correct |
1165 ms |
47028 KB |
Output is correct |
85 |
Correct |
1163 ms |
47032 KB |
Output is correct |
86 |
Correct |
839 ms |
30412 KB |
Output is correct |
87 |
Correct |
1097 ms |
32448 KB |
Output is correct |
88 |
Correct |
982 ms |
33528 KB |
Output is correct |
89 |
Correct |
1442 ms |
41420 KB |
Output is correct |