Submission #542545

#	Time	Username	Problem	Language	Result	Execution time	Memory
542545		chonka	Worst Reporter 4 (JOI21_worst_reporter4)	C++98	14 / 100	311 ms	63596 KiB

worst_reporter2

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

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

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 , ll > 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 ] ;
                }
            }
        }
    }
    ll 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 ) ;
                    }
                }
            }
            ll current = 1e17 ;
            ll 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 ( ) ;
            ll 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 (stderr)

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 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21