| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 624863 |
2022-08-08T22:43:11 Z |
chonka |
Pipes (BOI13_pipes) |
C++ |
|
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 ) ;
| ~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
