Submission #771783

#TimeUsernameProblemLanguageResultExecution timeMemory
771783gagik_2007Duathlon (APIO18_duathlon)C++17
23 / 100
946 ms1048576 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; ll ttt; const ll INF=1e18; const ll MOD=1e9+7; const ll N=3e5+7; ll n,m,k; vector<int>g[N]; ll sz[N]; void dfs(int v, int par=-1){ sz[v]=1; for(int to:g[v]){ if(to!=par){ dfs(to,v); sz[v]+=sz[to]; } } } void calc_ans(int c, int v, ll& ans, int par=-1){ ll sum=0; for(int to:g[v]){ if(to!=par){ calc_ans(c,to,ans,v); ans+=sz[to]*(c-sz[to]-1); sum+=sz[to]; } } ans+=sum*(c-sum-1); } int main() { cin>>n>>m; for(int i=0;i<m;i++){ int x,y; cin>>x>>y; g[x].push_back(y); g[y].push_back(x); } ll ans=0; for(int v=1;v<=n;v++){ if(sz[v]==0){ dfs(v); calc_ans(sz[v],v,ans); } } cout<<ans<<endl; }
#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...