Submission #624864

#	Time	Username	Problem	Language	Result	Execution time	Memory
624864		chonka	Pipes (BOI13_pipes)	C++98	65 / 100	132 ms	20048 KiB

pipes

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 1e5 + 7 ;

int n ;
int a[ MAXN ] , cnt[ MAXN ] ;
int ans[ MAXN ] ;
vector < pair < int , int > > v[ MAXN ] ;
vector < pair < int , int > > gr[ MAXN ] ;
bool used[ MAXN ] , done[ MAXN ] ;

pair < int , int > get ( int x , int add , int coef ) {
    used[ x ] = true ;
    for ( auto [ y , id ] : gr[ x ] ) {
        if ( used[ y ] == true ) { continue ; }
        get ( y , a[ y ] - add , -coef ) ;
    }
    return { add , coef } ;
}

void mrk ( int x , int val ) {
    used[ x ] = true ;
    for ( auto [ y , id ] : gr[ x ] ) {
        if ( used[ y ] == true ) { continue ; }
        ans[ id ] = 2 * val ;
        mrk ( y , a[ y ] - val ) ;
    }
}

void solve ( ) {
    int m ; 
    cin >> n >> m ;
    if ( m > n ) {
        cout << "0\n" ;
        return ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    for ( int i = 1 , x , y ; i <= m ; ++ i ) {
        cin >> x >> y ;
        v[ x ].push_back ( { y , i } ) ;
        v[ y ].push_back ( { x , i } ) ;
    }
    queue < int > q ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cnt[ i ] = ( int ) v[ i ].size ( ) ;
        if ( cnt[ i ] == 1 ) {
            cnt[ i ] = -1 ;
            q.push ( i ) ;
        }
    }
    while ( q.empty ( ) == false ) {
        int x = q.front ( ) ; q.pop ( ) ;
        done[ x ] = true ;
        for ( auto [ y , id ] : v[ x ] ) {
            if ( done[ y ] == true ) { continue ; }
            ans[ id ] += 2 * a[ x ] ; 
            a[ y ] -= ans[ id ] / 2 ;
            a[ x ] = 0 ;
            -- cnt[ y ] ;
            if ( cnt[ y ] == 1 ) {
                cnt[ y ] = -1 ;
                q.push ( y ) ;
            }
        }
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( cnt[ i ] > 0 ) {
            for ( auto [ y , id ] : v[ i ] ) {
                if ( cnt[ y ] > 0 ) {
                    gr[ i ].push_back ( { y , id } ) ;
                    gr[ y ].push_back ( { i , id } ) ;
                }
            }
        }
    }
    int edge_val ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( cnt[ i ] > 0 ) {
            auto ret = get ( i , 0 , 1 ) ;
            if ( ret.second == -1 ) {
                cout << "0\n" ;
                return ;
            }
            edge_val = ( a[ i ] - ret.first ) / 2 ;
            break ;
        }
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        used[ i ] = false ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( cnt[ i ] > 0 ) {
            mrk ( i , edge_val ) ;
            ans[ gr[ i ][ 1 ].second ] = 2 * ( a[ i ] - edge_val ) ;
            break ;
        }
    }
    for ( int i = 1 ; i <= m ; ++ i ) {
        cout << ans[ i ] << "\n" ;
    }
}

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

Compilation message (stderr)

pipes.cpp: In function 'std::pair<int, int> get(int, int, int)':
pipes.cpp:17:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for ( auto [ y , id ] : gr[ x ] ) {
      |                ^
pipes.cpp: In function 'void mrk(int, int)':
pipes.cpp:26:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for ( auto [ y , id ] : gr[ x ] ) {
      |                ^
pipes.cpp: In function 'void solve()':
pipes.cpp:59:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for ( auto [ y , id ] : v[ x ] ) {
      |                    ^
pipes.cpp:73:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |             for ( auto [ y , id ] : v[ i ] ) {
      |                        ^
pipes.cpp:98:17: warning: 'edge_val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |             mrk ( i , edge_val ) ;
      |             ~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 35 / 70