oj.uz

답안 #624865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624865 2022-08-08T22:48:10 Z chonka Pipes (BOI13_pipes) C++
65 / 100
 97 ms 18212 KB 
#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 } ) ;
                }
            }
        }
    }
    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

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:97:17: warning: 'edge_val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |             mrk ( i , edge_val ) ;
      |             ~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 60 ms 10628 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 4 ms 5076 KB Output is correct
13 Correct 51 ms 9540 KB Output is correct
14 Correct 55 ms 10336 KB Output is correct
15 Correct 63 ms 10700 KB Output is correct
16 Correct 51 ms 9796 KB Output is correct
17 Correct 53 ms 10700 KB Output is correct
18 Correct 56 ms 10748 KB Output is correct
19 Correct 61 ms 9924 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 57 ms 10708 KB Output is correct
23 Correct 45 ms 9588 KB Output is correct
24 Correct 68 ms 10764 KB Output is correct
25 Correct 50 ms 9780 KB Output is correct

Subtask #2
35.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Incorrect 70 ms 14176 KB Output isn't correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 2 ms 4948 KB Output isn't correct
8 Incorrect 3 ms 4968 KB Output isn't correct
9 Incorrect 2 ms 4948 KB Output isn't correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Incorrect 3 ms 4948 KB Output isn't correct
15 Incorrect 3 ms 5076 KB Output isn't correct
16 Incorrect 3 ms 5076 KB Output isn't correct
17 Incorrect 4 ms 5076 KB Output isn't correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Incorrect 3 ms 5076 KB Output isn't correct
23 Incorrect 52 ms 14028 KB Output isn't correct
24 Incorrect 80 ms 15156 KB Output isn't correct
25 Incorrect 65 ms 14180 KB Output isn't correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 4948 KB Output is correct
29 Correct 2 ms 4948 KB Output is correct
30 Incorrect 63 ms 14008 KB Output isn't correct
31 Incorrect 81 ms 18212 KB Output isn't correct
32 Incorrect 57 ms 11972 KB Output isn't correct
33 Incorrect 97 ms 15372 KB Output isn't correct
34 Correct 3 ms 4948 KB Output is correct
35 Correct 2 ms 4948 KB Output is correct
36 Correct 3 ms 4948 KB Output is correct
37 Correct 2 ms 4948 KB Output is correct
38 Incorrect 64 ms 14412 KB Output isn't correct
39 Incorrect 54 ms 11440 KB Output isn't correct
40 Incorrect 66 ms 14744 KB Output isn't correct
41 Incorrect 75 ms 18128 KB Output isn't correct
42 Correct 3 ms 4948 KB Output is correct
43 Correct 4 ms 4948 KB Output is correct
44 Correct 4 ms 4948 KB Output is correct
45 Correct 3 ms 4956 KB Output is correct
46 Incorrect 74 ms 13732 KB Output isn't correct
47 Incorrect 73 ms 14916 KB Output isn't correct
48 Incorrect 83 ms 17868 KB Output isn't correct
49 Incorrect 63 ms 11528 KB Output isn't correct
50 Correct 3 ms 4948 KB Output is correct
51 Correct 2 ms 4920 KB Output is correct
52 Correct 3 ms 4948 KB Output is correct
53 Correct 3 ms 4948 KB Output is correct
54 Incorrect 62 ms 13516 KB Output isn't correct