oj.uz

답안 #624863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624863 2022-08-08T22:43:11 Z chonka Pipes (BOI13_pipes) C++
35 / 100
 130 ms 20060 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 ] ;

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 ( ) ;
        for ( auto [ y , id ] : v[ x ] ) {
            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

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:58:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         for ( auto [ y , id ] : v[ x ] ) {
      |                    ^
pipes.cpp:71:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |             for ( auto [ y , id ] : v[ i ] ) {
      |                        ^
pipes.cpp:96:17: warning: 'edge_val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |             mrk ( i , edge_val ) ;
      |             ~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Incorrect 3 ms 5076 KB Output isn't correct
4 Incorrect 51 ms 10596 KB Output isn't correct
5 Incorrect 3 ms 4948 KB Output isn't correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Incorrect 2 ms 4948 KB Output isn't correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Incorrect 4 ms 5076 KB Output isn't correct
10 Incorrect 3 ms 5076 KB Output isn't correct
11 Incorrect 4 ms 5076 KB Output isn't correct
12 Incorrect 3 ms 5076 KB Output isn't correct
13 Incorrect 42 ms 9464 KB Output isn't correct
14 Incorrect 48 ms 10316 KB Output isn't correct
15 Incorrect 57 ms 10608 KB Output isn't correct
16 Incorrect 43 ms 9676 KB Output isn't correct
17 Incorrect 58 ms 10572 KB Output isn't correct
18 Incorrect 52 ms 10604 KB Output isn't correct
19 Incorrect 53 ms 9816 KB Output isn't correct
20 Incorrect 3 ms 4956 KB Output isn't correct
21 Incorrect 4 ms 5076 KB Output isn't correct
22 Incorrect 57 ms 10532 KB Output isn't correct
23 Incorrect 42 ms 9444 KB Output isn't correct
24 Incorrect 51 ms 10524 KB Output isn't correct
25 Incorrect 45 ms 9708 KB Output isn't correct

Subtask #2
35.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Incorrect 3 ms 5204 KB Output isn't correct
3 Incorrect 93 ms 15020 KB Output isn't correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Incorrect 3 ms 4948 KB Output isn't correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Incorrect 2 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 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2 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 79 ms 15064 KB Output isn't correct
24 Incorrect 81 ms 16168 KB Output isn't correct
25 Incorrect 67 ms 15096 KB Output isn't correct
26 Correct 2 ms 4948 KB Output is correct
27 Correct 2 ms 4948 KB Output is correct
28 Correct 4 ms 4948 KB Output is correct
29 Correct 3 ms 4948 KB Output is correct
30 Incorrect 95 ms 15040 KB Output isn't correct
31 Incorrect 101 ms 20060 KB Output isn't correct
32 Incorrect 61 ms 12244 KB Output isn't correct
33 Incorrect 90 ms 16384 KB Output isn't correct
34 Correct 2 ms 4948 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 3 ms 4948 KB Output is correct
37 Correct 4 ms 4948 KB Output is correct
38 Incorrect 76 ms 15260 KB Output isn't correct
39 Incorrect 58 ms 11468 KB Output isn't correct
40 Incorrect 75 ms 15720 KB Output isn't correct
41 Incorrect 106 ms 19972 KB Output isn't correct
42 Correct 3 ms 4948 KB Output is correct
43 Correct 3 ms 4948 KB Output is correct
44 Correct 2 ms 4948 KB Output is correct
45 Correct 2 ms 4948 KB Output is correct
46 Incorrect 69 ms 14552 KB Output isn't correct
47 Incorrect 92 ms 15816 KB Output isn't correct
48 Incorrect 130 ms 19684 KB Output isn't correct
49 Incorrect 60 ms 11708 KB Output isn't correct
50 Correct 3 ms 4948 KB Output is correct
51 Correct 2 ms 4948 KB Output is correct
52 Correct 2 ms 4948 KB Output is correct
53 Correct 3 ms 4948 KB Output is correct
54 Incorrect 78 ms 14132 KB Output isn't correct