Submission #1197466

#TimeUsernameProblemLanguageResultExecution timeMemory
1197466hackstarDuathlon (APIO18_duathlon)C++20
0 / 100
670 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; void solve(){ int n,m; cin>>n>>m; vector<vector<int>>g(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; u--,v--; g[u].emplace_back(v); g[v].emplace_back(u); } int ans=0; vector<int>dp(n); auto dfs=[&](auto dfs,int u,int p=-1)->void{ for(int v:g[u]){ if(u==p){ continue; } dp[v]=dp[u]+1; dfs(dfs,v,u); } ans+=max(0ll,dp[u]-2); }; for(int i=0;i<n;i++){ fill(all(dp),1); dfs(dfs,i); } 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...