이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N=1e5+1,M=2e5+1;
int n,m;
int d[N],low[N],vis[N];
vector<int>adj[N],ch[N];
int par[N],sz[N];
int ebc[N];
void dfs(int id,int p){
vis[id]=true;
sz[id]=1;
d[id]=low[id]=d[p]+1;
for(auto cur:adj[id]){
if(cur==p){
par[id]=p;continue;
}
if(vis[cur]){
low[id]=min(low[id],d[cur]);continue;
}
ch[id].pb(cur);
dfs(cur,id);
sz[id]+=sz[cur];
low[id]=min(low[id],low[cur]);
}
}
ll val[N];
void dfs2(int id){
if(low[id]<d[id]-1) ebc[id]=ebc[par[id]];
else ebc[id]=id;
int pcnt=1;
for(auto cur:ch[id]){
dfs2(cur);
if(ebc[cur]!=ebc[id]) val[ebc[cur]]+=1LL*(n-sz[cur])*(n-sz[cur]);
if(ebc[cur]!=ebc[id]) pcnt+=sz[cur];
}
val[ebc[id]]+=1LL*pcnt*pcnt;
}
ll ans;
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1; i<=m ;i++){
int u,v;cin >> u >> v;
adj[u].pb(v);adj[v].pb(u);
}
dfs(1,0);
dfs2(1);
ans=1LL*n*(n-1)*(n-1);
for(int i=1; i<=n ;i++){
int pcnt=1;
for(auto cur:ch[i]){
if(ebc[cur]!=ebc[i]) ans+=1LL*(n-sz[cur])*(n-sz[cur]);
if(ebc[cur]!=ebc[i]) ans-=val[ebc[cur]];
if(ebc[cur]!=ebc[i]) pcnt+=sz[cur];
}
ans+=1LL*pcnt*pcnt;
ans-=val[ebc[i]];
}
cout << ans << endl;
}
# | 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... |