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("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e5+5;
int n,n2,timer = 0;
vector<int>low(MAXN),tin(MAXN),sub(MAXN);
vii g(MAXN),g2(MAXN);
stack<int>stk;
ll ans = 0,cnt = 0;
void bbc(int v,int u){
cnt++;
tin[v] = low[v] = ++timer;
stk.push(v);
for(int x:g[v]){
if(x!= u){
if(!tin[x]){
bbc(x,v);
low[v] = min(low[v],low[x]);
if(low[x] >= tin[v]){
n2++;
g2[v].pb(n2);
g2[n2].pb(v);
while(g2[n2].back() != x){
g2[n2].pb(stk.top());
g2[stk.top()].pb(n2);
stk.pop();
}
}
}else{
low[v] = min(low[v],tin[x]);
}
}
}
}
void dfs(int v,int u){
sub[v] = (v<=n);
for(int x:g2[v]){
if(x != u){
dfs(x,v);
sub[v]+=sub[x];
}
}
}
void dfs2(int v,int u){
for(int x:g2[v]){
if(x != u){
dfs2(x,v);//c is in this bbc
if(v > n)ans-=(sz(g2[v]) - 1) * 1LL * sub[x] * 1LL *(sub[x]-1); //s and f is under this art vertex
}
}
if(v > n)ans-=(sz(g2[v])-1) * 1LL * (n-sub[v]) * 1LL * (n-sub[v]-1); //try parent as art vertex
}
int main()
{
int m;
cin>>n>>m;
n2 = n;
for(int i=0;i<m;i++){
int v,u;
cin>>v>>u;
g[v].pb(u);
g[u].pb(v);
}
for(int i=1;i<=n;i++){
if(!tin[i]){
cnt = 0;
bbc(i,-1);
dfs(i,-1);
//for(int i=1;i<=n2;i++)cout<<sub[i]<<" ";
dfs2(i,-1);
ans+=cnt*(cnt-1)*(cnt-2);
}
}
cout<<ans<<'\n';
}
# | 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... |