oj.uz

Submission #542544

# Submission time Handle Problem Language Result Execution time Memory
542544 2022-03-26T22:15:17 Z chonka Worst Reporter 4 (JOI21_worst_reporter4) C++
14 / 100
 132 ms 14524 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define MAXN 100007

struct stairs {
    map < int , ll > w ;
    stairs ( ) { w.clear ( ) ; }
    int get_sz ( ) { return w.size ( ) ; }

    void absorb ( stairs &other ) {
        for ( auto [ x , y ] : other.w ) {
            w[ x ] += y ;
        }
    }
    void add ( int pos , long long cost ) {
        w[ 0 ] += cost ;
        w[ pos ] -= cost ;
        w[ pos + 1 ] += cost ;
        auto it = w.find ( pos ) ;
        while ( 1 ) {
            auto hh = it ;
            -- hh ;
            if ( abs ( hh->second ) >= abs ( it->second ) ) {
                hh->second += it->second ;
                w.erase ( it ) ;
                break ;
            }
            else {
                it->second += hh->second ;
                w.erase ( hh ) ;
            }
        }
    }
};

int n ;
int nxt[ MAXN ] , a[ MAXN ] , cost[ MAXN ] ;
vector < int > v[ MAXN ] ;

bool used[ MAXN ] , in_cycle[ MAXN ] ;
int root[ MAXN ] ;


stairs dfs ( int vertex ) {
    stairs ans ;
    for ( auto x : v[ vertex ] ) {
        auto ret = dfs ( x ) ;
        if ( ans.get_sz ( ) < ret.get_sz ( ) ) {
            swap ( ans , ret ) ;
        }
        ans.absorb ( ret ) ;
    }
    ans.add ( a[ vertex ] , cost[ vertex ] ) ;
    return ans ;
}

void input ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> nxt[ i ] >> a[ i ] >> cost[ i ] ;
        v[ nxt[ i ] ].push_back ( i ) ;
    }
}

map < int , long long > cycle_vals ;

void solve ( ) {
    vector < int > aux ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( used[ i ] == false ) {
            int x = i ;
            aux.clear ( ) ;
            while ( used[ x ] == false ) {
                aux.push_back ( x ) ;
                used[ x ] = true ;
                x = nxt[ x ] ;
            }
            if ( root[ x ] == 0 ) {
                for ( auto y : aux ) {
                    root[ y ] = x ;
                }
            }
            else {
                for ( auto y : aux ) {
                    root[ y ] = root[ x ] ;
                }
            }
        }
    }
    long long ans = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( root[ i ] == i ) {
            aux.clear ( ) ;
            int x = i ;
            while ( in_cycle[ x ] == false ) {
                in_cycle[ x ] = true ;
                aux.push_back ( x ) ;
                x = nxt[ x ] ;
            }
            stairs hh ;
            for ( auto ori : aux ) {
                for ( auto vertex : v[ ori ] ) {
                    if ( in_cycle[ vertex ] == false ) {
                        stairs ret = dfs ( vertex ) ;
                        if ( hh.get_sz ( ) < ret.get_sz ( ) ) {
                            swap ( hh , ret ) ;
                        }
                        hh.absorb ( ret ) ;
                    }
                }
            }
            long long current = 1e17 ;
            long long tot = 0 ;
            cycle_vals.clear ( ) ;
            for ( auto vertex : aux ) {
                tot += cost[ vertex ] ;
                cycle_vals[ a[ vertex ] ] += cost[ vertex ] ;
            }
            cycle_vals[ 0 ] = 0 ;
            auto it = hh.w.begin ( ) ;
            long long outside = 0 ;
            for ( auto [ key , sm ] : cycle_vals ) {
                while ( it != hh.w.end ( ) && it->first <= key ) {
                    outside += it->second ;
                    ++ it ;
                }
                current = min ( current , outside + tot - sm ) ;
            }
            ans += current ;
        }
    }
    cout << ans << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    // cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

Compilation message

worst_reporter2.cpp: In member function 'void stairs::absorb(stairs&)':
worst_reporter2.cpp:14:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |         for ( auto [ x , y ] : other.w ) {
      |                    ^
worst_reporter2.cpp: In function 'void solve()':
worst_reporter2.cpp:125:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |             for ( auto [ key , sm ] : cycle_vals ) {
      |                        ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 6 ms 3208 KB Output is correct
6 Correct 5 ms 2900 KB Output is correct
7 Correct 5 ms 2900 KB Output is correct
8 Correct 7 ms 3204 KB Output is correct
9 Correct 6 ms 2936 KB Output is correct
10 Correct 5 ms 2900 KB Output is correct
11 Correct 4 ms 2900 KB Output is correct
12 Correct 6 ms 4104 KB Output is correct
13 Correct 5 ms 4052 KB Output is correct
14 Correct 6 ms 3556 KB Output is correct
15 Correct 5 ms 3540 KB Output is correct
16 Correct 6 ms 3284 KB Output is correct
17 Correct 6 ms 2928 KB Output is correct
18 Correct 4 ms 2900 KB Output is correct
19 Correct 6 ms 3668 KB Output is correct
20 Correct 5 ms 3452 KB Output is correct
21 Correct 4 ms 3456 KB Output is correct
22 Correct 5 ms 3156 KB Output is correct
23 Correct 5 ms 2932 KB Output is correct
24 Correct 7 ms 3724 KB Output is correct
25 Correct 4 ms 3540 KB Output is correct
26 Correct 7 ms 4436 KB Output is correct
27 Correct 7 ms 3668 KB Output is correct
28 Correct 5 ms 3844 KB Output is correct
29 Correct 5 ms 4052 KB Output is correct
30 Correct 5 ms 4052 KB Output is correct
31 Correct 5 ms 3976 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 6 ms 3208 KB Output is correct
6 Correct 5 ms 2900 KB Output is correct
7 Correct 5 ms 2900 KB Output is correct
8 Correct 7 ms 3204 KB Output is correct
9 Correct 6 ms 2936 KB Output is correct
10 Correct 5 ms 2900 KB Output is correct
11 Correct 4 ms 2900 KB Output is correct
12 Correct 6 ms 4104 KB Output is correct
13 Correct 5 ms 4052 KB Output is correct
14 Correct 6 ms 3556 KB Output is correct
15 Correct 5 ms 3540 KB Output is correct
16 Correct 6 ms 3284 KB Output is correct
17 Correct 6 ms 2928 KB Output is correct
18 Correct 4 ms 2900 KB Output is correct
19 Correct 6 ms 3668 KB Output is correct
20 Correct 5 ms 3452 KB Output is correct
21 Correct 4 ms 3456 KB Output is correct
22 Correct 5 ms 3156 KB Output is correct
23 Correct 5 ms 2932 KB Output is correct
24 Correct 7 ms 3724 KB Output is correct
25 Correct 4 ms 3540 KB Output is correct
26 Correct 7 ms 4436 KB Output is correct
27 Correct 7 ms 3668 KB Output is correct
28 Correct 5 ms 3844 KB Output is correct
29 Correct 5 ms 4052 KB Output is correct
30 Correct 5 ms 4052 KB Output is correct
31 Correct 5 ms 3976 KB Output is correct
32 Correct 6 ms 3156 KB Output is correct
33 Incorrect 132 ms 14524 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 6 ms 3208 KB Output is correct
6 Correct 5 ms 2900 KB Output is correct
7 Correct 5 ms 2900 KB Output is correct
8 Correct 7 ms 3204 KB Output is correct
9 Correct 6 ms 2936 KB Output is correct
10 Correct 5 ms 2900 KB Output is correct
11 Correct 4 ms 2900 KB Output is correct
12 Correct 6 ms 4104 KB Output is correct
13 Correct 5 ms 4052 KB Output is correct
14 Correct 6 ms 3556 KB Output is correct
15 Correct 5 ms 3540 KB Output is correct
16 Correct 6 ms 3284 KB Output is correct
17 Correct 6 ms 2928 KB Output is correct
18 Correct 4 ms 2900 KB Output is correct
19 Correct 6 ms 3668 KB Output is correct
20 Correct 5 ms 3452 KB Output is correct
21 Correct 4 ms 3456 KB Output is correct
22 Correct 5 ms 3156 KB Output is correct
23 Correct 5 ms 2932 KB Output is correct
24 Correct 7 ms 3724 KB Output is correct
25 Correct 4 ms 3540 KB Output is correct
26 Correct 7 ms 4436 KB Output is correct
27 Correct 7 ms 3668 KB Output is correct
28 Correct 5 ms 3844 KB Output is correct
29 Correct 5 ms 4052 KB Output is correct
30 Correct 5 ms 4052 KB Output is correct
31 Correct 5 ms 3976 KB Output is correct
32 Correct 6 ms 3156 KB Output is correct
33 Incorrect 132 ms 14524 KB Output isn't correct
34 Halted 0 ms 0 KB -