제출 #104949

#제출 시각아이디문제언어결과실행 시간메모리
104949puyu_liao철인 이종 경기 (APIO18_duathlon)C++14
0 / 100
110 ms18800 KiB
#include<bits/stdc++.h> #include<stdint.h> using namespace std; #define IOS {cin.tie(0);ios_base::sync_with_stdio(false);} #define N 300005 #define int int64_t vector<int> v[N]; int sz[N]; int ans = 0; bitset<N> vis,rt; void dfs(int x,int p){ vis[x] = 1; sz[x] = 1; for(int i : v[x]) if(i != p){ if(vis[i]) exit(-1); dfs(i,x); sz[x] += sz[i]; } } void dfs2(int x,int p,int sp,int sum){ int cnt = v[x].size(); for(int i : v[x]) if(i != p){ dfs2(i,x,sz[x]-sz[i],sum); if(cnt>1)ans += sz[i] * (sum - sz[i] - 1); } if(cnt > 1) ans += sp * (sum - sp - 1); } int32_t main(){ IOS; int n,m,a,b; cin >> n >> m; for(int i=0;i<m;i++){ cin >> a >> b; v[a].push_back(b); v[b].push_back(a); } //if(m!=n-1) return 0; for(int i=1;i<=n;i++) if(!vis[i]){ rt[i] = 1; dfs(i,i); } //for(int i=1;i<=n;i++) cout << sz[i] << '\n'; for(int i=1;i<=n;i++) if(rt[i]){ dfs2(i,i,0,sz[i]); } cout << ans << '\n'; return 0; }
#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...