# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
698633 | vjudge1 | Duathlon (APIO18_duathlon) | C++17 | 115 ms | 27968 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define maxn 200500
using namespace std;
int n,m;
vector<int> g[maxn];
bool vis[maxn];
int disc[maxn];
int low[maxn];
bool br[maxn];
int par[maxn];
int cnt[maxn];
int ct=0;
vector<pair<int,int> > b[maxn];
int sz[maxn];
void dfs(int u,int p=-1) {
vis[u]=true;
disc[u]=low[u]=ct++;
sz[u]=1;
for(auto v:g[u]) {
if(!vis[v]) {
dfs(v,u);
sz[u]+=sz[v];
par[v]=u;
low[u]=min(low[u],low[v]);
if(low[v]>disc[u]) {
br[v]=true;
}
}
else {
if(v!=p) low[u]=min(low[u],disc[v]);
}
}
}
void dfs_2(int u,int cur=1) {
vis[u]=true;
if(br[u]) cur=u;
for(auto v:g[u]) {
if(!vis[v]) {
if(br[v]) {
b[cur].push_back({u,v});
b[v].push_back({v,cur});
}
dfs_2(v,cur);
}
}
}
void dfs_3(int u,int p=-1) {
cnt[u]=sz[u];
for(auto v:b[u]) {
if(v.second!=p) {
cnt[u]-=sz[v.second];
dfs_3(v.second,u);
}
}
}
long long ans=0;
int mp[maxn];
void dfs_4(int u,int p=-1) {
int pc=n-sz[u];
vector<pair<int,int> > szs;
for(auto v:b[u]) {
if(v.second!=p) {
mp[v.first]+=sz[v.second];
}
else {
mp[v.first]+=(n-sz[u]);
}
}
for(auto v:b[u]) {
if(v.second!=p) {
szs.push_back({sz[v.second],mp[v.first]});
}
else {
szs.push_back({n-sz[u],mp[v.first]});
}
}
for(auto v:b[u]) {
mp[v.first]=0;
}
ans = ans+1ll*cnt[u]*(cnt[u]-1)*(cnt[u]-2);
//cout<<u<<" "<<ans<<endl;
for(auto c:szs) {
//cout<<"\t"<<c.first<<" "<<c.second<<endl;
int s=c.first;
int a=n-c.second-cnt[u];
if(cnt[u]>=2) {
ans=ans+2ll*(cnt[u]-1)*(cnt[u]-2)*s;
ans=ans+2ll*(cnt[u]-1)*s;
}
//cout<<u<<" "<<ans<<endl;
ans=ans+1ll*(cnt[u]-1)*s*a;
ans=ans+1ll*s*(n-s-cnt[u]);
//cout<<u<<" "<<ans<<endl;
}
//cout<<u<<" "<<ans<<endl;
for(auto v:b[u]) {
if(v.second!=p) dfs_4(v.second,u);
}
}
int main() {
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++) {
int u,v;
scanf("%d %d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
for(int i=1;i<=n;i++) vis[i]=false;
dfs_2(1);
dfs_3(1);
dfs_4(1);
printf("%lld",ans);
return 0;
}
Compilation message (stderr)
# | 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... |