This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int DIM = 1E5+7;
const int INF = 1E9;
vector<int> G[DIM];
vector<pair<int,int> > NG[DIM];
int depth[DIM],ptr = 0,P[DIM],vis[DIM],sub[DIM];
ll dp[DIM];
vector<int> V[DIM];
int fcmp(int v,int par){
depth[v] = depth[par]+1;
int mi = depth[v];
for(auto to:G[v]){
if (to==par)
continue;
if (depth[to]){
if (depth[to]<depth[v])
mi = min(mi,depth[to]);
continue;
}
mi = min(mi,fcmp(to,v));
}
if (v!=par && mi<depth[par])
P[v] = par;
else if (v!=par && mi==depth[par]) {
P[v] = v;
V[v].push_back(par);
NG[par].push_back({v, 0});
}
else {
P[v] = v;
if (v!=par)
NG[par].push_back({v,1});
}
return mi;
}
int F(int x){
return x==P[x]?x:P[x] = F(P[x]);
}
ll res = 0,ans = 0;
void dfs(int v){
vis[v] = 1;
int sz = int(V[v].size());
dp[v] = ll(sz-1)*(sz-2) + sz - 1;
ans+=ll(sz)*(sz-1)*(sz-2);
sub[v] = sz;
for(int ver:V[v]){
if (F(ver)!=v)
continue;
int su = 0;
for(auto [vto,type]:NG[ver]){
int to = F(vto);
if (to==v || vis[to])
continue;
dfs(to);
if (type==1) {
res += dp[to] * sub[v] + dp[v] * sub[to];
dp[v] = dp[v] + dp[to] + sub[to];
sub[v] += sub[to];
su += sub[to];
}
else{
res += dp[to]*(sub[v]-1)+dp[v]*(sub[to]-1)-ll(sub[to]-1)*(sub[v]-1);
dp[v] = dp[v] + dp[to];
sub[v]+=sub[to]-1;
su+=sub[to]-1;
}
}
dp[v]+=ll(sz-1)*su;
}
/*for(auto to:G[v]){
if (vis[to])
continue;
dfs(to);
res+=dp[to]*sub[v]+dp[v]*sub[to];
dp[v] = dp[v]+dp[to]+sz*sub[to];
sub[v]+=sub[to];
}*/
}
int solve(){
int n,m;
cin>>n>>m;
for(int i = 1;i<=m;++i){
ll u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = 1;i<=n;++i){
if (!P[i]) {
fcmp(i, i);
}
}
for(int i = 1;i<=n;++i){
V[F(i)].push_back(i);
}
for(int i = 1;i<=n;++i){
if (!V[i].empty() && !vis[i])
dfs(i);
}
cout<<res*2+ans<<endl;
return 1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |