| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1143987 | CSQ31 | 철인 이종 경기 (APIO18_duathlon) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 2e5+5;
struct edges{
int v,id;
edges(int _v,int _id):v(_v),id(_id){}
edges(){}
};
vector<edges>adj[MAXN];
vector<int>g[MAXN]; //edges of the block cut tree
int depth[MAXN],low[MAXN],visited[MAXN],art[MAXN];
int bcc = 0; //intialize this to n
ll num = 0;
stack<int>bcc_nodes;
void dfs(int u,int p,int root){
num++;
int child_cnt = 0;
bcc_nodes.push(u);
visited[u] = 1;
low[u] = depth[u];
for(auto [v,id]:adj[u]){
if(id == p)continue;
if(visited[v])low[u] = min(low[u],depth[v]);
else{
child_cnt++;
depth[v] = depth[u] + 1;
dfs(v,id,root);
low[u] = min(low[u],low[v]);
if(low[v] >= depth[u]){
bcc++;
g[u].push_back(bcc);
g[bcc].push_back(u);
while(g[bcc].back() != x){
int x = bcc_nodes.top();
g[x].push_back(bcc);
g[bcc].push_back(x);
bcc_nodes.pop();
}
}
}
}
}
int sub[MAXN],n;
ll ans = 0;
void dfs2(int v,int u){
sub[v] = v <= n;
for(int x:g[v]){
if(x==u)continue;
dfs2(x,v);
sub[v] += sub[x];
}
if(v<=n)return;
ll sum = 0;
for(int x:g[v]){
if(x==u)sum += (num-sub[v]) * 1LL * (num-sub[v]-1);
else sum += sub[x] * 1LL * (sub[x]-1);
}
ans -= sum * (g[v].size()-1);
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int m;
cin>>n>>m;
bcc = n;
for(int i=0;i<m;i++){
int v,u;
cin>>v>>u;
adj[v].push_back({u,i});
adj[u].push_back({v,i});
}
for(int i=1;i<=n;i++){
if(visited[i])continue;
num = 0;
dfs(i,-1,i);
ans += 1LL * num * (num-1) * (num-2);
dfs2(i,-1);
}
cout<<ans<<'\n';
}