Submission #698633

#TimeUsernameProblemLanguageResultExecution timeMemory
698633vjudge1Duathlon (APIO18_duathlon)C++17
0 / 100
115 ms27968 KiB
#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)

count_triplets.cpp: In function 'void dfs_4(int, int)':
count_triplets.cpp:59:9: warning: unused variable 'pc' [-Wunused-variable]
   59 |     int pc=n-sz[u];
      |         ^~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...