oj.uz

답안 #624862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624862 2022-08-08T22:38:20 Z chonka Pipes (BOI13_pipes) C++
35 / 100
 101 ms 21468 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 ] = 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 ;
        }
    }
    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 ] = a[ i ] - edge_val ;
        }
    }
    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:49: warning: 'edge_val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |             ans[ gr[ i ][ 1 ].second ] = a[ i ] - edge_val ;
      |                                          ~~~~~~~^~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 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 54 ms 12132 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 3 ms 4928 KB Output isn't correct
8 Incorrect 3 ms 5028 KB Output isn't correct
9 Incorrect 3 ms 5076 KB Output isn't correct
10 Incorrect 3 ms 5076 KB Output isn't correct
11 Incorrect 3 ms 5076 KB Output isn't correct
12 Incorrect 3 ms 5044 KB Output isn't correct
13 Incorrect 41 ms 10668 KB Output isn't correct
14 Incorrect 54 ms 11772 KB Output isn't correct
15 Incorrect 69 ms 12176 KB Output isn't correct
16 Incorrect 48 ms 11112 KB Output isn't correct
17 Incorrect 52 ms 12132 KB Output isn't correct
18 Incorrect 55 ms 12172 KB Output isn't correct
19 Incorrect 56 ms 11356 KB Output isn't correct
20 Incorrect 3 ms 4948 KB Output isn't correct
21 Incorrect 3 ms 5076 KB Output isn't correct
22 Incorrect 73 ms 12156 KB Output isn't correct
23 Incorrect 43 ms 10656 KB Output isn't correct
24 Incorrect 52 ms 12116 KB Output isn't correct
25 Incorrect 43 ms 10960 KB Output isn't correct

Subtask #2
35.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5032 KB Output isn't correct
2 Incorrect 3 ms 5204 KB Output isn't correct
3 Incorrect 68 ms 16460 KB Output isn't correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Incorrect 2 ms 5036 KB Output isn't correct
9 Incorrect 3 ms 4948 KB Output isn't correct
10 Correct 3 ms 5032 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 5028 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Incorrect 2 ms 5028 KB Output isn't correct
15 Incorrect 3 ms 5204 KB Output isn't correct
16 Incorrect 3 ms 5076 KB Output isn't correct
17 Incorrect 3 ms 5132 KB Output isn't correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Incorrect 3 ms 5076 KB Output isn't correct
23 Incorrect 66 ms 16460 KB Output isn't correct
24 Incorrect 79 ms 17652 KB Output isn't correct
25 Incorrect 70 ms 16476 KB Output isn't correct
26 Correct 3 ms 5076 KB Output is correct
27 Correct 3 ms 5076 KB Output is correct
28 Correct 2 ms 5040 KB Output is correct
29 Correct 2 ms 5076 KB Output is correct
30 Incorrect 76 ms 16468 KB Output isn't correct
31 Incorrect 99 ms 21440 KB Output isn't correct
32 Incorrect 60 ms 13748 KB Output isn't correct
33 Incorrect 76 ms 17916 KB Output isn't correct
34 Correct 3 ms 5040 KB Output is correct
35 Correct 3 ms 5076 KB Output is correct
36 Correct 2 ms 5076 KB Output is correct
37 Correct 3 ms 5076 KB Output is correct
38 Incorrect 73 ms 16752 KB Output isn't correct
39 Incorrect 56 ms 13004 KB Output isn't correct
40 Incorrect 73 ms 17268 KB Output isn't correct
41 Incorrect 98 ms 21468 KB Output isn't correct
42 Correct 2 ms 5076 KB Output is correct
43 Correct 3 ms 5044 KB Output is correct
44 Correct 2 ms 5076 KB Output is correct
45 Correct 3 ms 5048 KB Output is correct
46 Incorrect 74 ms 16036 KB Output isn't correct
47 Incorrect 78 ms 17320 KB Output isn't correct
48 Incorrect 101 ms 21284 KB Output isn't correct
49 Incorrect 57 ms 13232 KB Output isn't correct
50 Correct 2 ms 5076 KB Output is correct
51 Correct 3 ms 5044 KB Output is correct
52 Correct 2 ms 5040 KB Output is correct
53 Correct 2 ms 5076 KB Output is correct
54 Incorrect 71 ms 15692 KB Output isn't correct