제출 #1197446

#제출 시각아이디문제언어결과실행 시간메모리
1197446hackstar철인 이종 경기 (APIO18_duathlon)C++20
0 / 100
1093 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); } vector<vector<int>>dist(n,vector<int>(n,inf)); for (int i=0;i<n;++i){ dist[i][i]=0; for (int to:g[i]){ dist[i][to]=1; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); } } } 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...