#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=3e5+7;
const ll LG=25;
ll n,m,k;
vector<int>g[N];
bool used[N];
bool cikli_papa[N];
int cikl[N];
int a[N];
vector<int>cikler;
set<pair<int,int>>koxer;
vector<int>gg[N];
int up[N][LG];
int dist[N][LG];
int tin[N],tout[N];
int timer=0;
bool arinq[N];
int comp[N];
int ciklGti(int p, int v, int par){
used[v]=true;
for(int to:g[v]){
if(!used[to]){
int res=ciklGti(p, to, v);
if(res!=-1){
if(cikli_papa[v])cikl[p]=v;
return res + 1;
}
}
else if(to==p&&to!=par){
if(cikli_papa[v])cikl[p]=v;
return 1;
}
}
return -1;
}
void dfs(int v, int par=-1){
tin[v]=timer++;
up[v][0]=(par==-1?v:par);
dist[v][0]=(par==-1?0:a[par]);
for(int to:gg[v]){
if(to!=par){
dfs(to,v);
}
}
tout[v]=timer++;
}
bool is_papa(int v, int u){
return (tin[v]<=tin[u]&&tout[v]>=tout[u]);
}
void lca_precalc() {
for(int i=1;i<LG;i++){
for(int v=1;v<=n;v++){
up[v][i]=up[up[v][i-1]][i-1];
dist[v][i]=dist[v][i-1]+dist[up[v][i-1]][i-1];
}
}
}
int lca(int v, int u){
if(is_papa(v,u))return v;
if(is_papa(u,v))return u;
for(int i=LG-1;i>=0;i--){
if(!is_papa(up[v][i],u)){
v=up[v][i];
}
}
return up[v][0];
}
int find_dist(int v, int u){
if(v==u)return a[v];
int papa=lca(u,v);
int ans=0;
for(int i=LG-1;i>=0;i--){
if(!is_papa(up[v][i],papa)){
ans+=dist[v][i];
v=up[v][i];
}
}
for(int i=LG-1;i>=0;i--){
if(!is_papa(up[u][i],papa)){
ans+=dist[u][i];
u=up[u][i];
}
}
ans+=a[v];
ans+=a[u];
if(papa!=v&&papa!=u){
ans+=a[papa];
}
return ans;
}
void findComp(int c, int v){
comp[v]=c;
for(int to:g[v]){
if(comp[to]==0){
findComp(c,to);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int v=1;v<=n;v++){
fill(used,used+n+1,false);
int res=ciklGti(v,v,v);
if(res!=-1){
if(cikl[v]==0){
cikl[v]=v;
cikli_papa[v]=true;
cikler.push_back(v);
a[v]=res;
}
}
else{
cikl[v]=v;
cikler.push_back(v);
a[v]=1;
}
}
// cout<<endl;
// for(int v:cikler)cout<<v<<" "<<a[v]<<endl;
// cout<<endl;
// for(int v=1;v<=n;v++){
// cout<<cikl[v]<<" ";
// }
// cout<<endl;
for(int v=1;v<=n;v++){
for(int to:g[v]){
if(cikl[v]!=cikl[to])
koxer.insert({cikl[v],cikl[to]});
if(cikl[v]!=cikl[to])
koxer.insert({cikl[to],cikl[v]});
}
}
for(auto e:koxer){
gg[e.ff].push_back(e.ss);
gg[e.ss].push_back(e.ff);
}
for(int v:cikler){
if(tout[v]==0){
dfs(v);
}
}
lca_precalc();
int cur=1;
for(int v=1;v<=n;v++){
if(comp[v]==0){
findComp(cur++,v);
}
}
ll ans=0;
for(int v:cikler){
for(int u:cikler){
if(u!=v&&comp[u]==comp[v]){
int cur=find_dist(u,v);
ans+=cur-a[u]-a[v];
ans+=(cur-a[u]-1)*(a[v]-1);
ans+=(cur-a[v]-1)*(a[u]-1);
ans+=(cur-2)*(a[v]-1)*(a[u]-1);
}
}
}
for(int v:cikler){
ans+=a[v]*(a[v]-1)*(a[v]-2);
}
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1068 ms |
26700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
266 ms |
14848 KB |
Output is correct |
| 2 |
Correct |
270 ms |
14816 KB |
Output is correct |
| 3 |
Correct |
526 ms |
14844 KB |
Output is correct |
| 4 |
Execution timed out |
1083 ms |
14816 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1066 ms |
19096 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
14844 KB |
Output is correct |
| 2 |
Correct |
738 ms |
14840 KB |
Output is correct |
| 3 |
Execution timed out |
1057 ms |
14804 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1060 ms |
19004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
