Submission #402154

#TimeUsernameProblemLanguageResultExecution timeMemory
402154A_DDuathlon (APIO18_duathlon)C++14
0 / 100
120 ms11580 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N=1e5+100; vector<int> g[N]; int dep[N]; int a[N]; int n,ans; void dfs2(int u,int p) { for(auto x:g[u]){ if(x==p)continue; dep[x]=dep[u]+1; dfs2(x,u); a[u]+=a[x]; } } void dfs(int u,int p,int ann) { ans+=ann-(n); //cout<<u<<" "<<ann<<endl; ans+=1; for(auto x:g[u]){ if(x==p)continue; dfs(x,u,ann+(n-a[x])-a[x]); } } void solve() { int m,ann=0; cin>>n>>m; if(m!=n-1)assert(0); for(int i=1;i<=n;i++)a[i]=1; while(m--){ int a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } dfs2(1,1); for(int i=1;i<=n;i++){ ann+=dep[i]; } dfs(1,1,ann); cout<<ans<<endl; } main() { int t=1; // cin>>t; while(t--)solve(); }

Compilation message (stderr)

count_triplets.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main()
      | ^~~~
#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...