| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 624864 |
2022-08-08T22:46:28 Z |
chonka |
Pipes (BOI13_pipes) |
C++ |
|
132 ms |
20048 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 } ) ;
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: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 ) ;
| ~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5088 KB |
Output is correct |
| 4 |
Correct |
53 ms |
10668 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 |
5036 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 10 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 11 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 12 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 13 |
Correct |
47 ms |
9532 KB |
Output is correct |
| 14 |
Correct |
51 ms |
10388 KB |
Output is correct |
| 15 |
Correct |
52 ms |
10700 KB |
Output is correct |
| 16 |
Correct |
50 ms |
9872 KB |
Output is correct |
| 17 |
Correct |
65 ms |
10664 KB |
Output is correct |
| 18 |
Correct |
53 ms |
10700 KB |
Output is correct |
| 19 |
Correct |
53 ms |
9916 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 22 |
Correct |
53 ms |
10736 KB |
Output is correct |
| 23 |
Correct |
40 ms |
9544 KB |
Output is correct |
| 24 |
Correct |
74 ms |
10676 KB |
Output is correct |
| 25 |
Correct |
53 ms |
9816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
5108 KB |
Output isn't correct |
| 3 |
Incorrect |
70 ms |
15096 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
2 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 |
3 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 |
2 ms |
4948 KB |
Output isn't correct |
| 15 |
Incorrect |
5 ms |
5204 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 |
4 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 22 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 23 |
Incorrect |
64 ms |
15212 KB |
Output isn't correct |
| 24 |
Incorrect |
79 ms |
16280 KB |
Output isn't correct |
| 25 |
Incorrect |
70 ms |
15032 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 |
3 ms |
4948 KB |
Output is correct |
| 30 |
Incorrect |
101 ms |
15012 KB |
Output isn't correct |
| 31 |
Incorrect |
132 ms |
20048 KB |
Output isn't correct |
| 32 |
Incorrect |
72 ms |
12284 KB |
Output isn't correct |
| 33 |
Incorrect |
83 ms |
16496 KB |
Output isn't correct |
| 34 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 35 |
Correct |
3 ms |
5016 KB |
Output is correct |
| 36 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 37 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 38 |
Incorrect |
80 ms |
15372 KB |
Output isn't correct |
| 39 |
Incorrect |
63 ms |
11648 KB |
Output isn't correct |
| 40 |
Incorrect |
85 ms |
15772 KB |
Output isn't correct |
| 41 |
Incorrect |
105 ms |
20040 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 |
3 ms |
4948 KB |
Output is correct |
| 45 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 46 |
Incorrect |
77 ms |
14624 KB |
Output isn't correct |
| 47 |
Incorrect |
81 ms |
15876 KB |
Output isn't correct |
| 48 |
Incorrect |
100 ms |
19632 KB |
Output isn't correct |
| 49 |
Incorrect |
66 ms |
11880 KB |
Output isn't correct |
| 50 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 51 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 52 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 53 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 54 |
Incorrect |
94 ms |
14252 KB |
Output isn't correct |
