Submission #104957

#TimeUsernameProblemLanguageResultExecution timeMemory
104957puyu_liaoDuathlon (APIO18_duathlon)C++14
0 / 100
141 ms17628 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 sum) { for(int i : v[x]) { if(i != p) dfs2(i, x, sum), ans += sz[i] * (sum - sz[i] - 1); else ans += (sum - sz[x]) * (sz[x] - 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); } dfs(1,1); dfs2(1,1,sz[1]); 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...