oj.uz

Submission #252972

# Submission time Handle Problem Language Result Execution time Memory
252972 2020-07-26T14:46:43 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 ;
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] ;
        }
}
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 ( 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 Runtime error 665 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 665 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1110 ms 339928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 4 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 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 2 ms 2816 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 3 ms 2816 KB Output is correct
13 Correct 4 ms 2688 KB Output is correct
14 Correct 3 ms 2688 KB Output is correct
15 Correct 3 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 3 ms 2688 KB Output is correct
18 Correct 3 ms 2816 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 153 ms 10032 KB Output is correct
2 Correct 141 ms 9960 KB Output is correct
3 Correct 153 ms 9980 KB Output is correct
4 Correct 136 ms 9976 KB Output is correct
5 Correct 134 ms 9976 KB Output is correct
6 Correct 156 ms 13688 KB Output is correct
7 Correct 148 ms 12792 KB Output is correct
8 Correct 151 ms 12152 KB Output is correct
9 Correct 143 ms 11384 KB Output is correct
10 Correct 136 ms 9976 KB Output is correct
11 Correct 169 ms 9976 KB Output is correct
12 Correct 131 ms 9976 KB Output is correct
13 Correct 131 ms 10076 KB Output is correct
14 Correct 132 ms 9864 KB Output is correct
15 Correct 125 ms 9592 KB Output is correct
16 Correct 70 ms 8440 KB Output is correct
17 Correct 114 ms 10220 KB Output is correct
18 Correct 110 ms 10212 KB Output is correct
19 Correct 109 ms 10208 KB Output is correct
20 Correct 113 ms 10216 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 3 ms 2816 KB Output is correct
3 Runtime error 742 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 150 ms 9976 KB Output is correct
2 Correct 149 ms 9852 KB Output is correct
3 Runtime error 993 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 Runtime error 665 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 665 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -