//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
llo n,m;
vector<llo> adj[100001];
llo vis[100001];
llo par[100001];
llo ind[100001];
vector<llo> ss;
set<llo> adj2[100001];
llo val[100001];
vector<llo> pre[100001];
llo par5[100001];
void dfs(llo no,llo par2=-1){
ss.pb(no);
vis[no]=1;
par5[no]=par2;
par[no]=no;
for(auto j:adj[no]){
if(j!=par2){
if(vis[j]==0){
dfs(j,no);
}
else if(par[j]!=no){
vector<llo> cot;
llo cur=no;
while(cur!=j){
cot.pb(cur);
cur=par5[cur];
}
cot.pb(cur);
for(auto ii:cot){
par[ii]=j;
}
}
}
}
}
llo par3[100001];
llo ans=0;
void dfs2(llo no,llo par2=-1){
par3[no]=par2;
//val[no]=1;
//ss.pb(no);
// vis[no]=1;
llo su=0;
for(auto j:adj2[no]){
if(j!=par2){
dfs2(j,no);
su+=val[j];
val[no]+=val[j];
}
}
for(auto j:adj2[no]){
if(j!=par2){
//cout<<no<<":"<<j<<":"<<(val[j]*(su-val[j])*(val[no]-su))<<endl;
ans+=(val[j]*(su-val[j])*(val[no]-su));
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(llo i=0;i<m;i++){
llo aa,bb;
cin>>aa>>bb;
aa--;
bb--;
adj[aa].pb(bb);
adj[bb].pb(aa);
}
for(llo i=0;i<n;i++){
if(vis[i]==0){
ss.clear();
//dfs2(i);
/* for(auto j:ss){
ans+=2*(val[j]-1)*(ss.size()-val[j]);
//cout<<j<<":";
}*/
//cout<<endl;
//continue;
dfs(i);
for(auto j:ss){
val[par[j]]++;
for(auto ii:adj[j]){
if(par[j]!=par[ii]){
adj2[par[j]].insert(par[ii]);
}
}
}
//continue;
for(auto j:ss){
pre[par[j]].pb(j);
}
dfs2(i);
/*for(auto j:ss){
cout<<j<<":"<<par[j]<<":"<<val[j]<<endl;
}*/
llo nn=ss.size();
for(auto j:ss){
if(par[j]==j){
llo aa=pre[j].size();
if(aa>=3){
ans+=((((aa*(aa-1)*(aa-2)))));
}
ans+=2*(val[j]-aa)*aa*(nn-val[j]);
//continue;
llo co2=0;
if(aa>=2){
for(auto ii:pre[j]){
if(ii!=j){
llo co=ss.size();
co-=aa;
for(auto k:adj[ii]){
if(k!=par5[ii] and par[k]!=par[ii]){
co-=val[k];
co2+=val[k];
}
}
ans+=2*(aa-1)*co;
// cout<<ii<<":"<<(2*(aa-1))*co<<":"<<co<<endl;
}
}
ans+=2*(aa-1)*co2;
//cout<<j<<":"<<(2*(aa-1))*co2<<endl;
}
}
}
}
}
cout<<ans<<endl;
// dfs(0);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
30196 KB |
Output is correct |
2 |
Correct |
92 ms |
30424 KB |
Output is correct |
3 |
Correct |
115 ms |
30004 KB |
Output is correct |
4 |
Correct |
130 ms |
31480 KB |
Output is correct |
5 |
Correct |
109 ms |
25844 KB |
Output is correct |
6 |
Correct |
115 ms |
28732 KB |
Output is correct |
7 |
Correct |
119 ms |
27396 KB |
Output is correct |
8 |
Correct |
145 ms |
28544 KB |
Output is correct |
9 |
Correct |
121 ms |
25872 KB |
Output is correct |
10 |
Correct |
109 ms |
25908 KB |
Output is correct |
11 |
Correct |
94 ms |
22640 KB |
Output is correct |
12 |
Correct |
107 ms |
22720 KB |
Output is correct |
13 |
Correct |
117 ms |
22572 KB |
Output is correct |
14 |
Correct |
81 ms |
22324 KB |
Output is correct |
15 |
Correct |
69 ms |
22144 KB |
Output is correct |
16 |
Correct |
68 ms |
21796 KB |
Output is correct |
17 |
Correct |
17 ms |
16760 KB |
Output is correct |
18 |
Correct |
17 ms |
16716 KB |
Output is correct |
19 |
Correct |
17 ms |
16664 KB |
Output is correct |
20 |
Correct |
17 ms |
16716 KB |
Output is correct |
21 |
Correct |
21 ms |
16772 KB |
Output is correct |
22 |
Correct |
17 ms |
16704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
9948 KB |
Output is correct |
2 |
Correct |
7 ms |
9932 KB |
Output is correct |
3 |
Correct |
7 ms |
9932 KB |
Output is correct |
4 |
Correct |
6 ms |
9932 KB |
Output is correct |
5 |
Correct |
7 ms |
9932 KB |
Output is correct |
6 |
Correct |
7 ms |
9932 KB |
Output is correct |
7 |
Correct |
7 ms |
9932 KB |
Output is correct |
8 |
Correct |
8 ms |
9932 KB |
Output is correct |
9 |
Correct |
7 ms |
9932 KB |
Output is correct |
10 |
Correct |
7 ms |
9932 KB |
Output is correct |
11 |
Correct |
7 ms |
9932 KB |
Output is correct |
12 |
Correct |
7 ms |
9932 KB |
Output is correct |
13 |
Correct |
7 ms |
9932 KB |
Output is correct |
14 |
Correct |
7 ms |
9804 KB |
Output is correct |
15 |
Correct |
6 ms |
9804 KB |
Output is correct |
16 |
Correct |
6 ms |
9804 KB |
Output is correct |
17 |
Correct |
6 ms |
9932 KB |
Output is correct |
18 |
Correct |
6 ms |
9932 KB |
Output is correct |
19 |
Correct |
7 ms |
9932 KB |
Output is correct |
20 |
Correct |
6 ms |
9932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
151 ms |
30564 KB |
Output is correct |
2 |
Correct |
162 ms |
30772 KB |
Output is correct |
3 |
Correct |
136 ms |
30568 KB |
Output is correct |
4 |
Correct |
134 ms |
30576 KB |
Output is correct |
5 |
Correct |
140 ms |
30644 KB |
Output is correct |
6 |
Correct |
159 ms |
36876 KB |
Output is correct |
7 |
Correct |
149 ms |
34956 KB |
Output is correct |
8 |
Correct |
142 ms |
33840 KB |
Output is correct |
9 |
Correct |
139 ms |
32708 KB |
Output is correct |
10 |
Correct |
154 ms |
30344 KB |
Output is correct |
11 |
Correct |
162 ms |
30564 KB |
Output is correct |
12 |
Correct |
134 ms |
30072 KB |
Output is correct |
13 |
Correct |
145 ms |
30024 KB |
Output is correct |
14 |
Correct |
144 ms |
28724 KB |
Output is correct |
15 |
Correct |
114 ms |
27488 KB |
Output is correct |
16 |
Correct |
72 ms |
23812 KB |
Output is correct |
17 |
Correct |
132 ms |
30776 KB |
Output is correct |
18 |
Correct |
132 ms |
30768 KB |
Output is correct |
19 |
Correct |
128 ms |
30832 KB |
Output is correct |
20 |
Correct |
127 ms |
30736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9932 KB |
Output is correct |
2 |
Correct |
7 ms |
9932 KB |
Output is correct |
3 |
Incorrect |
6 ms |
9804 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
139 ms |
30580 KB |
Output is correct |
2 |
Correct |
151 ms |
30480 KB |
Output is correct |
3 |
Incorrect |
132 ms |
26760 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |