Submission #124967

#TimeUsernameProblemLanguageResultExecution timeMemory
124967elabensaadDuathlon (APIO18_duathlon)C++14
23 / 100
1146 ms1048580 KiB
#include <bits/stdc++.h> using namespace std; long long n, m, x, y, vis[300000], ans; vector <int> t[300000]; void DFS (int v){ vis[v] = 1; for (auto i : t[v]){ if (vis[i] == 0){DFS(i);vis[v] += vis[i]; } } } void dfs (int v, int r, int p = 0){ ans+=(vis[r]-vis[v])*(vis[v]-1)*2; for (auto i : t[v]){ if (i != p){dfs(i, r, v);ans+=(vis[v]-vis[i]-1)*vis[i];} } } main() { cin >> n >> m; for(int i = 0;i < m;i++){ cin >> x >> y; x--; y--; t[x].push_back(y); t[y].push_back(x); } for (int i = 0; i < n; i++){ if (vis[i] == 0){ DFS(i); dfs(i, i); } } cout << ans; }

Compilation message (stderr)

count_triplets.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 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...