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