Submission #252991

#TimeUsernameProblemLanguageResultExecution timeMemory
252991infinite_iqDuathlon (APIO18_duathlon)C++14
31 / 100
927 ms1048580 KiB
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <bits/stdc++.h> using namespace std; #define sqr 340 #define mp make_pair #define mid (l+r)/2 #define le node * 2 #define ri node * 2 + 1 #define pb push_back #define ppb pop_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define ins insert #define era erase #define C continue #define mem(dp,i) memset(dp,i,sizeof(dp)) #define mset multiset #define all(x) x.begin(), x.end() #define gc getchar_unlocked typedef long long ll; typedef short int si; typedef long double ld; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; typedef pair<double,ll>pdi; const ll inf=1e18; const ll mod=987654321; const ld Pi=acos(-1); ll n , m , ans , nodes , edges ; vll v [100009] ; ll dp [100009] , done [100009] ; ; void calc ( int node ) { if ( done [node] ) return ; done [node] = 1 ; nodes ++ , edges += v [node] .size () ; for ( auto u : v [node] ) calc ( u ) ; } void solve ( int node , int p ) { dp [node] = 1 ; for ( auto u : v [node] ) { if ( u == p ) C ; solve ( u , node ) ; dp [node] += dp [u] ; } ll sum = 0 , up = nodes - dp [node] ; for ( auto u : v [node] ) { if ( u == p ) C ; ans += up * dp [u] * 2ll ; ans += sum * dp [u] * 2ll ; sum += dp [u] ; } } int main () { cin >> n >> m ; for ( int i = 0 ; i < m ; i ++ ) { int a , b ; cin >> a >> b ; a -- , b -- ; v [a] .pb ( b ) ; v [b] .pb ( a ) ; } for ( int i = 0 ; i < n ; i ++ ) { if ( done [i] ) C ; nodes = 0 , edges = 0 ; calc ( i ) ; if ( nodes * 2ll == edges ) { if ( nodes >= 3ll ) { ans += ( nodes ) * ( nodes - 1ll ) * ( nodes - 2ll ) ; } } else solve ( i , i ) ; } cout << ans << endl ; }
#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...