#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
vi dfsNum;
vi dfsLow;
ll currDfsNum = 0;
vector<vi> e;
set<pii> bridges;
void dfs(ll v, ll l){
if(dfsNum[v]!=-1) return;
dfsNum[v] = dfsLow[v] = currDfsNum++;
rep(i,0,e[v].size()){
if(e[v][i]==l) continue;
dfs(e[v][i],v);
dfsLow[v] = min(dfsLow[v],dfsLow[e[v][i]]);
}
}
vector<vi> cycles;
vi cycleIndices;
vector<bool> seen;
void getCycle(ll v){
if(seen[v]) return;
seen[v] = true;
cycles[cycles.size()-1].push_back(v);
cycleIndices[v] = cycles.size()-1;
rep(i,0,e[v].size()){
if(bridges.find({v,e[v][i]})==bridges.end())
getCycle(e[v][i]);
}
}
vector<vi> treeE;
vector<vi> dp;
ll getNum(ll v,ll l, ll toPlace){
seen[v] = true;
//cout<<v<<" "<<toPlace-1<<endl;
if(dp[v][toPlace-1]!=-1) return dp[v][toPlace-1];
ll ans = 0;
ll sz = cycles[v].size();
if(toPlace==1)
ans += sz; //1 here
if(toPlace==2)
ans += (sz-1)*(sz-1);//2 here
if(toPlace==3)
ans += (sz)*(sz-1)*(sz-2); //3 here
ll childSum = 0;
rep(i,0,treeE[v].size())
if(treeE[v][i] != l)
childSum += getNum(treeE[v][i],v,1);
rep(i,0,treeE[v].size()){
if(treeE[v][i] == l) continue;
if(toPlace==1)
ans += getNum(treeE[v][i],v,1);//no here
if(toPlace==2){
ans += getNum(treeE[v][i],v,1)*sz;//1 here
ans += getNum(treeE[v][i],v,2);//no here
}
if(toPlace==3){
ll childNum = getNum(treeE[v][i],v,1);
ans += (sz-1)*(sz-1)*childNum*2; //2 here
ans += childNum*(childSum - childNum)*sz;//c here
ans += getNum(treeE[v][i],v,2)*sz*2;//f or s here
ans += getNum(treeE[v][i],v,3);//no here
}
}
return dp[v][toPlace-1] = ans;
}
ll n,m;
ll brute(){
ll ans = 0;
set<ll> bridgeNodes;
rep(i,0,n){
bool bridgeNode = false;
rep(j,0,e[i].size()){
if(dfsNum[e[i][j]]>dfsNum[i]&&dfsLow[e[i][j]]>=dfsNum[i]){
bridgeNode = true;
}
}
if(bridgeNode) {
//cout<<i+1<<endl;
bridgeNodes.insert(i);
}
}
rep(s,0,n)
rep(c,0,n)
rep(f,0,n){
if(s==c||c==f||f==s)
continue;
bool fail = false;
set<ll> bridgeNodes1;
set<ll> bridgeNodes2;
rep(w,0,2){
swap(bridgeNodes1,bridgeNodes2);
ll from,to;
if(w==0){
from = s;
to = c;
} else {
from = c;
to = f;
}
vi p(n,-1);
queue<pii> q;
q.push({from,-2});
while(q.size()){
ll v = q.front().first;
ll parent = q.front().second;
q.pop();
if(p[v]!=-1) continue;
p[v] = parent;
rep(i,0,e[v].size())
q.push({e[v][i],v});
}
if(p[to]==-1) fail = true;
ll v = to;
bridgeNodes1.insert(to);
bridgeNodes1.insert(from);
while(p[v]!=-2){
v = p[v];
if(bridgeNodes.find(v)!=bridgeNodes.end()){
bridgeNodes1.insert(v);
}
}
}
trav(v,bridgeNodes1){
if(bridgeNodes2.find(v)!=bridgeNodes2.end()&&v!=c){
fail = true;
}
}
ans += !fail;
}
return ans;
}
int main(){
cin.sync_with_stdio(false);
cin>>n>>m;
e.resize(n);
dfsNum.resize(n,-1);
dfsLow.resize(n,-1);
vector<pii> edges(m);
rep(i,0,m){
ll a,b;
cin>>a>>b;
--a; --b;
edges[i] = {a,b};
e[a].push_back(b);
e[b].push_back(a);
}
rep(i,0,n)
dfs(i,-1);
//cout<<endl<<endl;
rep(i,0,n){
//cout<<i+1<<": "<<dfsNum[i]<<" "<<dfsLow[i]<<endl;
}
rep(i,0,m){
ll a,b;
tie(a,b) = edges[i];
if(dfsNum[a]<dfsNum[b]&&dfsLow[b]==dfsNum[b]){
bridges.insert({a,b});
bridges.insert({b,a});
}
if(dfsNum[b]<dfsNum[a]&&dfsLow[a]==dfsNum[a]){
bridges.insert({a,b});
bridges.insert({b,a});
}
}
cout<<brute()<<endl;
return 0;
cycleIndices.resize(n);
seen.resize(n);
rep(i,0,n){
if(seen[i]) continue;
cycles.push_back(vi(0));
getCycle(i);
}
treeE.resize(cycles.size());
trav(bridge,bridges){
//cout<<bridge.first+1<<" "<<bridge.second+1<<endl;
if(bridge.first<bridge.second){
ll a = cycleIndices[bridge.first];
ll b = cycleIndices[bridge.second];
treeE[a].push_back(b);
treeE[b].push_back(a);
}
}
ll ans = 0;
/*
rep(i,0,cycles.size()){
ll sz = cycles[i].size();
ans += (sz)*(sz-1)*(sz-2);
}*/
dp.resize(cycles.size(),vi(3,-1));
seen.assign(cycles.size(),false);
rep(i,0,cycles.size()){
if(!seen[i]) ans+=getNum(i,-1,3);
}
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1083 ms |
15872 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1085 ms |
15872 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
27084 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1068 ms |
27084 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
27092 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
