Submission #402150

#TimeUsernameProblemLanguageResultExecution timeMemory
402150A_DDuathlon (APIO18_duathlon)C++14
0 / 100
1118 ms1048580 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; 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:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | 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...