Submission #1197455

#TimeUsernameProblemLanguageResultExecution timeMemory
1197455hackstarDuathlon (APIO18_duathlon)C++20
0 / 100
1123 ms1114112 KiB
#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include<bits/stdc++.h> using namespace std; using namespace __gnu_pbds; template <typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; template <typename T> using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>; #pragma GCC optimize("Ofast,O3,unroll-loops") #pragma GCC target("avx,avx2") #define int long long #define ll long long #define pii pair<int,int> #define ff first #define ss second #define vi vector<int> #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() template<typename T1,typename T2> istream& operator>>(istream& cin,pair<T1,T2>& s){ cin>>s.first>>s.second; return cin; } template<typename T1,typename T2> ostream& operator<<(ostream& cout,pair<T1,T2>& s){ cout<<s.first<<' '<<s.second<<'\n'; return cout; } template<typename T> istream& operator>>(istream& cin,vector<T>& a){ for(T& x:a){ cin>>x; } return cin; } template<typename T> ostream& operator<<(ostream& cout,vector<T>& a){ for(T& x:a){ cout<<x<<' '; } return cout; } const int inf=1e18; struct LCA { int n, LOG; vector<vector<pair<int, int>>> g; vector<vector<int>> up; vector<int> depth; vector<int> dist; LCA(int _n) : n(_n) { LOG = ceil(log2(n)) + 1; g.resize(n); up.assign(n, vector<int>(LOG, -1)); depth.resize(n); dist.resize(n, 0); } void add(int u, int v, int w = 1) { g[u].push_back({v, w}); g[v].push_back({u, w}); } void dfs(int v, int p) { for (auto &[u, w] : g[v]) { if (u == p) continue; up[u][0] = v; dist[u] = dist[v] + w; depth[u] = depth[v] + 1; for (int i = 1; i < LOG; i++) { if (up[u][i - 1] != -1) up[u][i] = up[up[u][i - 1]][i - 1]; } dfs(u, v); } } void init(int root = 0) { depth[root] = 0; dist[root] = 0; dfs(root, -1); } int get_lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); for (int i = LOG - 1; i >= 0; i--) { if (depth[u] - (1 << i) >= depth[v]) u = up[u][i]; } if (u == v) return u; for (int i = LOG - 1; i >= 0; i--) { if (up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } } return up[u][0]; } int get_distance(int u, int v) { int lca = get_lca(u, v); return dist[u] + dist[v] - 2 * dist[lca]; } auto get_graph() { return g; } }; void solve(){ int n,m; cin>>n>>m; LCA lca(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; u--,v--; lca.add(u,v); } lca.init(); auto dist=[&](int u,int v)->int{ return lca.get_distance(u,v); }; int ans=0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==j){ continue; } int cur=dist(i,j)-1; ans+=max(0ll,cur); } } cout<<ans; } signed main(){ cin.tie(nullptr)->sync_with_stdio(false); int t=1; #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif //cin>>t; while(t--){ solve(); } }
#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...