oj.uz

Submission #252977

# Submission time Handle Problem Language Result Execution time Memory
252977 2020-07-26T14:55:55 Z infinite_iq Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#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 , timer = 1 , ans , crnt ;
vll v [100009] ;
ll done [100009] , color [100009] , dp [100009] , sz [100009] ;
void dfs ( int node , int p ) {
        color [node] = timer ;
        sz [timer] ++ ;
        dp [node] = 1 ;
        for ( auto u :v [node] ) {
                if ( u == p ) C ;
                dfs ( u , node ) ;
                dp [node] += dp [u] ;
        }
}
void solve ( int node , int p ) {
        done [node] = 1 ;
        ll sum = 0 , up = sz [ color [node] ] - dp [node] ;
        for ( auto u : v [node] ) {
                if ( u == p ) C ;
                solve ( u , node ) ;
                ans += sum * dp [u] ;
                ans += up  * dp [u] ;
                sum += dp [u] ;
        }
}
void go ( int node ) {
        crnt ++ ;
        done [node] = 1 ;
        for ( auto u : v [node] ) {
                if ( done [u] ) C ;
                go ( 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 ) ;
        }
        if ( m == n ) {
                for ( int i = 0 ; i < n ; i ++ ) {
                        if ( done [i] ) C ;
                        crnt = 0 ;
                        go ( i ) ;
                        if ( crnt >= 3ll ) {
                                ans += crnt * ( crnt-1 ) * ( crnt-2 ) ;
                        }
                }
                cout << ans << endl ;
                exit (0) ;
        }
        for ( int i = 0 ; i < n ; i ++ ) {
                if ( color [i] ) C ;
                dfs ( i , i ) ;
                timer ++ ;
        }
        for ( int i = 0 ; i < n ; i ++ ) {
                if ( done [i] ) C ;
                solve ( i , i ) ;
        }
        cout << ans * 2ll << endl ;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Runtime error 555 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Runtime error 555 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 11000 KB Output is correct
2 Correct 126 ms 11004 KB Output is correct
3 Execution timed out 1116 ms 391360 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2720 KB Output is correct
2 Correct 3 ms 2816 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 3 ms 2816 KB Output is correct
10 Correct 3 ms 2688 KB Output is correct
11 Correct 3 ms 2944 KB Output is correct
12 Correct 3 ms 2688 KB Output is correct
13 Correct 3 ms 2688 KB Output is correct
14 Correct 2 ms 2816 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 3 ms 2816 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 3 ms 2816 KB Output is correct
20 Correct 3 ms 2816 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 9976 KB Output is correct
2 Correct 132 ms 9976 KB Output is correct
3 Correct 133 ms 9976 KB Output is correct
4 Correct 137 ms 10104 KB Output is correct
5 Correct 134 ms 9976 KB Output is correct
6 Correct 163 ms 13688 KB Output is correct
7 Correct 144 ms 12792 KB Output is correct
8 Correct 166 ms 12096 KB Output is correct
9 Correct 145 ms 11256 KB Output is correct
10 Correct 145 ms 9976 KB Output is correct
11 Correct 134 ms 10108 KB Output is correct
12 Correct 133 ms 9976 KB Output is correct
13 Correct 140 ms 9976 KB Output is correct
14 Correct 120 ms 9724 KB Output is correct
15 Correct 117 ms 9464 KB Output is correct
16 Correct 67 ms 8440 KB Output is correct
17 Correct 111 ms 10216 KB Output is correct
18 Correct 128 ms 10352 KB Output is correct
19 Correct 119 ms 10208 KB Output is correct
20 Correct 125 ms 10216 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Runtime error 680 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 10056 KB Output is correct
2 Correct 145 ms 9860 KB Output is correct
3 Runtime error 913 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Runtime error 555 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Runtime error 555 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -