#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define fi first
#define se second
#define PB push_back
#define uint unsigned
#define int long long
using namespace std;
const int N=100050;
int n,m,fa[N];
set<int> ch[N],e[N],r[N],in[N];
ll ans;
ll calc(int x){
return ch[x].size()*1LL*(ch[x].size()-1)+in[x].size()*1LL*ch[x].size();
}
void add(int x,int c){ ans+=(calc(x)*c); }
int SZ(int x){ return ch[x].size()+e[x].size()+r[x].size()+in[x].size(); }
int unite(int u,int v){
if (ch[u].empty()) return v;
if (ch[v].empty()) return u;
add(u,-1); add(v,-1);
e[v].erase(e[v].find(u));
r[u].erase(r[u].find(v));
if (SZ(u)>SZ(v)) swap(u,v);
for (int x:ch[u]) {
if (in[v].find(x)!=in[v].end()) {
in[v].erase(in[v].find(x));
}
ch[v].insert(x);
fa[x]=v;
}
ch[u].clear();
for (int x:in[u]) {
if (ch[v].find(x)==ch[v].end()) {
in[v].insert(x);
}
}
in[u].clear();
vector<int> adj;
for (int x:e[u]) {
if (r[v].find(x)!=r[v].end()) {
adj.PB(x);
}
r[x].erase(r[x].find(u));
if (e[v].find(x)==e[v].end()) {
e[v].insert(x);
r[x].insert(v);
}
}
e[u].clear();
for (int x:r[u]) {
if (e[v].find(x)!=e[v].end()) {
adj.PB(x);
}
e[x].erase(e[x].find(u));
if (r[v].find(x)==r[v].end()) {
r[v].insert(x);
e[x].insert(v);
}
}
r[u].clear();
add(v,1);
sort(adj.begin(),adj.end());
adj.erase(unique(adj.begin(),adj.end()),adj.end());
for (int x:adj) if (v!=x) v=unite(v,x);
return v;
}
signed main(){
scanf("%lld%lld",&n,&m);
For(i,1,n){
ch[i].insert(i);
fa[i]=i;
}
while(m--) {
int a,b;
scanf("%lld%lld",&a,&b);
int u=fa[a],v=fa[b];
if (u!=v) {
if (e[v].find(u)!=e[v].end()) {
unite(u,v);
} else {
add(v,-1);
in[v].insert(a);
e[u].insert(v);
r[v].insert(u);
add(v,1);
}
}
printf("%lld\n",ans);
}
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%lld%lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~
joitter2.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%lld%lld",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19028 KB |
Output is correct |
2 |
Correct |
9 ms |
18984 KB |
Output is correct |
3 |
Correct |
10 ms |
19028 KB |
Output is correct |
4 |
Correct |
9 ms |
19028 KB |
Output is correct |
5 |
Correct |
10 ms |
19028 KB |
Output is correct |
6 |
Correct |
10 ms |
19116 KB |
Output is correct |
7 |
Correct |
11 ms |
19144 KB |
Output is correct |
8 |
Correct |
12 ms |
19096 KB |
Output is correct |
9 |
Correct |
15 ms |
19032 KB |
Output is correct |
10 |
Correct |
11 ms |
19028 KB |
Output is correct |
11 |
Correct |
10 ms |
19028 KB |
Output is correct |
12 |
Correct |
10 ms |
19028 KB |
Output is correct |
13 |
Correct |
11 ms |
19096 KB |
Output is correct |
14 |
Correct |
10 ms |
19008 KB |
Output is correct |
15 |
Correct |
10 ms |
19092 KB |
Output is correct |
16 |
Correct |
10 ms |
19112 KB |
Output is correct |
17 |
Correct |
12 ms |
19028 KB |
Output is correct |
18 |
Correct |
11 ms |
19028 KB |
Output is correct |
19 |
Correct |
10 ms |
19028 KB |
Output is correct |
20 |
Correct |
13 ms |
19108 KB |
Output is correct |
21 |
Correct |
14 ms |
19156 KB |
Output is correct |
22 |
Correct |
10 ms |
19028 KB |
Output is correct |
23 |
Correct |
13 ms |
19104 KB |
Output is correct |
24 |
Correct |
10 ms |
19028 KB |
Output is correct |
25 |
Correct |
10 ms |
19028 KB |
Output is correct |
26 |
Correct |
10 ms |
19028 KB |
Output is correct |
27 |
Correct |
10 ms |
19128 KB |
Output is correct |
28 |
Correct |
10 ms |
19028 KB |
Output is correct |
29 |
Correct |
10 ms |
19028 KB |
Output is correct |
30 |
Correct |
13 ms |
19108 KB |
Output is correct |
31 |
Correct |
11 ms |
19028 KB |
Output is correct |
32 |
Correct |
11 ms |
19068 KB |
Output is correct |
33 |
Correct |
11 ms |
19112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19028 KB |
Output is correct |
2 |
Correct |
9 ms |
18984 KB |
Output is correct |
3 |
Correct |
10 ms |
19028 KB |
Output is correct |
4 |
Correct |
9 ms |
19028 KB |
Output is correct |
5 |
Correct |
10 ms |
19028 KB |
Output is correct |
6 |
Correct |
10 ms |
19116 KB |
Output is correct |
7 |
Correct |
11 ms |
19144 KB |
Output is correct |
8 |
Correct |
12 ms |
19096 KB |
Output is correct |
9 |
Correct |
15 ms |
19032 KB |
Output is correct |
10 |
Correct |
11 ms |
19028 KB |
Output is correct |
11 |
Correct |
10 ms |
19028 KB |
Output is correct |
12 |
Correct |
10 ms |
19028 KB |
Output is correct |
13 |
Correct |
11 ms |
19096 KB |
Output is correct |
14 |
Correct |
10 ms |
19008 KB |
Output is correct |
15 |
Correct |
10 ms |
19092 KB |
Output is correct |
16 |
Correct |
10 ms |
19112 KB |
Output is correct |
17 |
Correct |
12 ms |
19028 KB |
Output is correct |
18 |
Correct |
11 ms |
19028 KB |
Output is correct |
19 |
Correct |
10 ms |
19028 KB |
Output is correct |
20 |
Correct |
13 ms |
19108 KB |
Output is correct |
21 |
Correct |
14 ms |
19156 KB |
Output is correct |
22 |
Correct |
10 ms |
19028 KB |
Output is correct |
23 |
Correct |
13 ms |
19104 KB |
Output is correct |
24 |
Correct |
10 ms |
19028 KB |
Output is correct |
25 |
Correct |
10 ms |
19028 KB |
Output is correct |
26 |
Correct |
10 ms |
19028 KB |
Output is correct |
27 |
Correct |
10 ms |
19128 KB |
Output is correct |
28 |
Correct |
10 ms |
19028 KB |
Output is correct |
29 |
Correct |
10 ms |
19028 KB |
Output is correct |
30 |
Correct |
13 ms |
19108 KB |
Output is correct |
31 |
Correct |
11 ms |
19028 KB |
Output is correct |
32 |
Correct |
11 ms |
19068 KB |
Output is correct |
33 |
Correct |
11 ms |
19112 KB |
Output is correct |
34 |
Correct |
12 ms |
19236 KB |
Output is correct |
35 |
Correct |
95 ms |
24908 KB |
Output is correct |
36 |
Correct |
150 ms |
27944 KB |
Output is correct |
37 |
Correct |
121 ms |
28020 KB |
Output is correct |
38 |
Correct |
162 ms |
27608 KB |
Output is correct |
39 |
Correct |
13 ms |
19248 KB |
Output is correct |
40 |
Correct |
14 ms |
19392 KB |
Output is correct |
41 |
Correct |
13 ms |
19412 KB |
Output is correct |
42 |
Correct |
11 ms |
19248 KB |
Output is correct |
43 |
Correct |
12 ms |
19356 KB |
Output is correct |
44 |
Correct |
12 ms |
19412 KB |
Output is correct |
45 |
Correct |
13 ms |
19212 KB |
Output is correct |
46 |
Correct |
12 ms |
19156 KB |
Output is correct |
47 |
Correct |
15 ms |
19412 KB |
Output is correct |
48 |
Correct |
13 ms |
19376 KB |
Output is correct |
49 |
Correct |
23 ms |
20268 KB |
Output is correct |
50 |
Correct |
129 ms |
27940 KB |
Output is correct |
51 |
Correct |
18 ms |
19632 KB |
Output is correct |
52 |
Correct |
111 ms |
26344 KB |
Output is correct |
53 |
Correct |
19 ms |
20052 KB |
Output is correct |
54 |
Correct |
119 ms |
27240 KB |
Output is correct |
55 |
Correct |
17 ms |
19828 KB |
Output is correct |
56 |
Correct |
17 ms |
19788 KB |
Output is correct |
57 |
Correct |
18 ms |
20232 KB |
Output is correct |
58 |
Correct |
16 ms |
20180 KB |
Output is correct |
59 |
Correct |
14 ms |
19284 KB |
Output is correct |
60 |
Correct |
111 ms |
24136 KB |
Output is correct |
61 |
Correct |
14 ms |
19376 KB |
Output is correct |
62 |
Correct |
127 ms |
27444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19028 KB |
Output is correct |
2 |
Correct |
9 ms |
18984 KB |
Output is correct |
3 |
Correct |
10 ms |
19028 KB |
Output is correct |
4 |
Correct |
9 ms |
19028 KB |
Output is correct |
5 |
Correct |
10 ms |
19028 KB |
Output is correct |
6 |
Correct |
10 ms |
19116 KB |
Output is correct |
7 |
Correct |
11 ms |
19144 KB |
Output is correct |
8 |
Correct |
12 ms |
19096 KB |
Output is correct |
9 |
Correct |
15 ms |
19032 KB |
Output is correct |
10 |
Correct |
11 ms |
19028 KB |
Output is correct |
11 |
Correct |
10 ms |
19028 KB |
Output is correct |
12 |
Correct |
10 ms |
19028 KB |
Output is correct |
13 |
Correct |
11 ms |
19096 KB |
Output is correct |
14 |
Correct |
10 ms |
19008 KB |
Output is correct |
15 |
Correct |
10 ms |
19092 KB |
Output is correct |
16 |
Correct |
10 ms |
19112 KB |
Output is correct |
17 |
Correct |
12 ms |
19028 KB |
Output is correct |
18 |
Correct |
11 ms |
19028 KB |
Output is correct |
19 |
Correct |
10 ms |
19028 KB |
Output is correct |
20 |
Correct |
13 ms |
19108 KB |
Output is correct |
21 |
Correct |
14 ms |
19156 KB |
Output is correct |
22 |
Correct |
10 ms |
19028 KB |
Output is correct |
23 |
Correct |
13 ms |
19104 KB |
Output is correct |
24 |
Correct |
10 ms |
19028 KB |
Output is correct |
25 |
Correct |
10 ms |
19028 KB |
Output is correct |
26 |
Correct |
10 ms |
19028 KB |
Output is correct |
27 |
Correct |
10 ms |
19128 KB |
Output is correct |
28 |
Correct |
10 ms |
19028 KB |
Output is correct |
29 |
Correct |
10 ms |
19028 KB |
Output is correct |
30 |
Correct |
13 ms |
19108 KB |
Output is correct |
31 |
Correct |
11 ms |
19028 KB |
Output is correct |
32 |
Correct |
11 ms |
19068 KB |
Output is correct |
33 |
Correct |
11 ms |
19112 KB |
Output is correct |
34 |
Correct |
12 ms |
19236 KB |
Output is correct |
35 |
Correct |
95 ms |
24908 KB |
Output is correct |
36 |
Correct |
150 ms |
27944 KB |
Output is correct |
37 |
Correct |
121 ms |
28020 KB |
Output is correct |
38 |
Correct |
162 ms |
27608 KB |
Output is correct |
39 |
Correct |
13 ms |
19248 KB |
Output is correct |
40 |
Correct |
14 ms |
19392 KB |
Output is correct |
41 |
Correct |
13 ms |
19412 KB |
Output is correct |
42 |
Correct |
11 ms |
19248 KB |
Output is correct |
43 |
Correct |
12 ms |
19356 KB |
Output is correct |
44 |
Correct |
12 ms |
19412 KB |
Output is correct |
45 |
Correct |
13 ms |
19212 KB |
Output is correct |
46 |
Correct |
12 ms |
19156 KB |
Output is correct |
47 |
Correct |
15 ms |
19412 KB |
Output is correct |
48 |
Correct |
13 ms |
19376 KB |
Output is correct |
49 |
Correct |
23 ms |
20268 KB |
Output is correct |
50 |
Correct |
129 ms |
27940 KB |
Output is correct |
51 |
Correct |
18 ms |
19632 KB |
Output is correct |
52 |
Correct |
111 ms |
26344 KB |
Output is correct |
53 |
Correct |
19 ms |
20052 KB |
Output is correct |
54 |
Correct |
119 ms |
27240 KB |
Output is correct |
55 |
Correct |
17 ms |
19828 KB |
Output is correct |
56 |
Correct |
17 ms |
19788 KB |
Output is correct |
57 |
Correct |
18 ms |
20232 KB |
Output is correct |
58 |
Correct |
16 ms |
20180 KB |
Output is correct |
59 |
Correct |
14 ms |
19284 KB |
Output is correct |
60 |
Correct |
111 ms |
24136 KB |
Output is correct |
61 |
Correct |
14 ms |
19376 KB |
Output is correct |
62 |
Correct |
127 ms |
27444 KB |
Output is correct |
63 |
Correct |
507 ms |
72248 KB |
Output is correct |
64 |
Correct |
486 ms |
72380 KB |
Output is correct |
65 |
Correct |
470 ms |
72416 KB |
Output is correct |
66 |
Correct |
216 ms |
28952 KB |
Output is correct |
67 |
Correct |
399 ms |
35272 KB |
Output is correct |
68 |
Correct |
189 ms |
28932 KB |
Output is correct |
69 |
Correct |
416 ms |
35984 KB |
Output is correct |
70 |
Correct |
201 ms |
28948 KB |
Output is correct |
71 |
Correct |
220 ms |
28904 KB |
Output is correct |
72 |
Correct |
430 ms |
35308 KB |
Output is correct |
73 |
Correct |
509 ms |
35420 KB |
Output is correct |
74 |
Correct |
967 ms |
48080 KB |
Output is correct |
75 |
Correct |
570 ms |
41760 KB |
Output is correct |
76 |
Correct |
806 ms |
46892 KB |
Output is correct |
77 |
Correct |
791 ms |
46868 KB |
Output is correct |
78 |
Correct |
237 ms |
34756 KB |
Output is correct |
79 |
Correct |
403 ms |
38132 KB |
Output is correct |
80 |
Correct |
242 ms |
34756 KB |
Output is correct |
81 |
Correct |
394 ms |
38032 KB |
Output is correct |
82 |
Correct |
890 ms |
56456 KB |
Output is correct |
83 |
Correct |
838 ms |
56368 KB |
Output is correct |
84 |
Correct |
802 ms |
75352 KB |
Output is correct |
85 |
Correct |
786 ms |
75136 KB |
Output is correct |
86 |
Correct |
305 ms |
29720 KB |
Output is correct |
87 |
Correct |
304 ms |
31996 KB |
Output is correct |
88 |
Correct |
403 ms |
35336 KB |
Output is correct |
89 |
Correct |
732 ms |
45848 KB |
Output is correct |