Submission #603172

#TimeUsernameProblemLanguageResultExecution timeMemory
603172LunaMemeDuathlon (APIO18_duathlon)C++14
0 / 100
118 ms14072 KiB
#include <bits/stdc++.h> using namespace std; typedef vector<int> vi; typedef long long ll; #define PB push_back #define FOR(i, x, y) for (int i =x; i < y; i ++) ll f(ll n){ return (1LL * n * (n - 1) * (n - 2)) /3; } ll g(ll l){ return 1LL * (l -1) * (l - 2); } ll ans = 0; int n, m; const int MAXN = 1e5 + 5; vi adj[MAXN]; int sz[MAXN], par[MAXN]; int find(int a){ if (a == par[a]) return a; return par[a] = find(par[a]); } void onion(int a, int b){ a = find(a); b = find(b); //cout << a << ' ' << b << '\n'; if (a == b) return; if (sz[a] < sz[b]) swap(a, b); sz[a] += sz[b]; sz[b] = 1; par[b] = par[a]; } int dist[MAXN] = { -1 }; void dfs(int curr, int nodes){ for (auto next : adj[curr]){ if (dist[next] >= 0 && dist[next] == dist[curr] - 1) continue; //cout << curr << " -> " << next << '\n'; if (dist[next] >= 0){//cycle int c_length = dist[curr] + 1 - dist[next]; //cout << next << ' ' << c_length << '\n'; ans += 2*f(c_length) + 1LL* (nodes- c_length)* g(c_length); dist[next] = dist[curr] + 1; } else{ dist[next] = dist[curr] + 1; dfs(next, nodes); } } } int main(){ cin >> n >> m; FOR(i, 1, n + 1){ par[i] = i; sz[i] = 1; } FOR(i, 0, m){ int a, b; cin >> a >> b; adj[a].PB(b); adj[b].PB(a); onion(a, b); } //bfs for each component int visited[MAXN] = { 0 }; memset(dist, -1, sizeof dist); FOR(i, 1, n+ 1){ if (visited[find(i)]) continue; int a = find(i); visited[a] = 1; ans += f(sz[a]); dist[i] = 0; dfs(i, sz[a]); } cout << ans; }
#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...