oj.uz

Submission #221964

# Submission time Handle Problem Language Result Execution time Memory
221964 2020-04-11T15:51:39 Z infinite_iq Pipes (BOI13_pipes) C++14
44.0741 / 100
 872 ms 91256 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll inf=1e18;
const ld pai=acos(-1);
ll n , m , all ;
set<pll>v[500009];
ll val[500009] , ans[500009] , ret[500009] , VAL[500009] ,done[500009];;
ll start ;
ll calc(int node , ll p ){
        done [node] = 1 ;
        ll ret = 0 ;
        for ( auto u : v[node] ) {
                if ( done [u.fi] ) C ;
                ret = calc ( u.fi , val[u.fi] - p) ;
                break ;
        }
        return ret + p ;
}
void solve ( int node) {
        done [node] = 1 ;
        ll out = 0 ;
        for ( auto u : v[node] ) {
                if ( done [u.fi] ) C ;
                val[u.fi] -= val[node] ;
                ans [ u.se ] = val[node];
                solve( u.fi ) ;
                out = 1 ;
                break;
        }
        if ( !out ) {
                for ( auto u :v[node] ) {
                        if ( u.fi == start ) {
                                ans [ u.se ] = val[ node];
                                break ;
                        }
                }
        }
}
int main () {
        mem ( ret , -1 ) ;
        cin >> n >> m ;
        for ( int i = 0 ; i < n ; i ++ ) cin >> val[i] ;
        for ( int i = 0 ; i < m ; i ++ ) {
                int a , b ;
                cin >> a >> b ;
                a -- , b -- ;
                v[a].ins( { b , i } ) ;
                v[b].ins( { a , i } ) ;
        }
        if ( m > n ) {
                cout << 0 << endl ;
                exit ( 0 ) ;
        }
        set<pll>s;
        for ( int i = 0 ; i < n ; i ++ ) {
                s.ins ( { v[i].size() , i } ) ;
        }
        while ( ( s.size() && s.begin()->fi==1 ) ) {
                int node = s.begin() -> se ;
                int to = v[node].begin() -> fi ;
                int id = v[node].begin() -> se ;
                s.era(s.begin());
                v[node].era( v[node].begin() );
                s.era ( { v[to].size() , to } ) ;
                v[to].era( { node , id } ) ;
                if ( v[to].size() ) s.ins ( { v[to].size() , to } ) ;
                ans [ id ] = -val [ node ] ;
                val [ to ] += val[node];
                val [ node ] = 0 ;
        }
        if ( s.size() && s.size() % 2 == 0 ) cout << 0 << endl , exit ( 0 ) ;
        if ( !s.size() ) {
                for ( int i = 0 ; i < m ; i ++ ) {
                        cout << -ans [i] *2 << endl ;
                }
                exit ( 0 ) ;
        }
        for ( auto u : s ) all += val[u.se] ;
        all /= 2;
        start = s.begin()->se;
        val[start] = all - calc ( 0 , 0 ) ;
        mem(done,0);
        solve(0);
        for ( int i = 0 ;i < m ;i ++ ) cout << -ans[i]*2 << endl;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 27776 KB Output isn't correct
2 Incorrect 21 ms 27776 KB Output isn't correct
3 Incorrect 24 ms 27904 KB Output isn't correct
4 Incorrect 526 ms 48504 KB Output isn't correct
5 Incorrect 21 ms 27776 KB Output isn't correct
6 Incorrect 21 ms 27776 KB Output isn't correct
7 Incorrect 20 ms 27776 KB Output isn't correct
8 Incorrect 20 ms 27776 KB Output isn't correct
9 Incorrect 23 ms 27904 KB Output isn't correct
10 Incorrect 28 ms 28032 KB Output isn't correct
11 Incorrect 25 ms 27904 KB Output isn't correct
12 Incorrect 24 ms 27904 KB Output isn't correct
13 Incorrect 401 ms 44280 KB Output isn't correct
14 Incorrect 488 ms 47352 KB Output isn't correct
15 Incorrect 504 ms 48504 KB Output isn't correct
16 Incorrect 438 ms 45392 KB Output isn't correct
17 Incorrect 517 ms 48632 KB Output isn't correct
18 Incorrect 526 ms 48596 KB Output isn't correct
19 Incorrect 482 ms 48820 KB Output isn't correct
20 Incorrect 21 ms 27776 KB Output isn't correct
21 Incorrect 24 ms 27904 KB Output isn't correct
22 Incorrect 518 ms 48552 KB Output isn't correct
23 Incorrect 398 ms 44280 KB Output isn't correct
24 Incorrect 536 ms 48632 KB Output isn't correct
25 Incorrect 431 ms 45048 KB Output isn't correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 31872 KB Output isn't correct
2 Incorrect 24 ms 31872 KB Output isn't correct
3 Correct 259 ms 46968 KB Output is correct
4 Correct 174 ms 40952 KB Output is correct
5 Correct 177 ms 40788 KB Output is correct
6 Correct 837 ms 91132 KB Output is correct
7 Incorrect 23 ms 31616 KB Output isn't correct
8 Incorrect 22 ms 31616 KB Output isn't correct
9 Correct 20 ms 27776 KB Output is correct
10 Correct 23 ms 27776 KB Output is correct
11 Correct 20 ms 27776 KB Output is correct
12 Correct 20 ms 27776 KB Output is correct
13 Correct 20 ms 27776 KB Output is correct
14 Incorrect 22 ms 31616 KB Output isn't correct
15 Incorrect 26 ms 31872 KB Output isn't correct
16 Incorrect 26 ms 31872 KB Output isn't correct
17 Correct 22 ms 27904 KB Output is correct
18 Correct 21 ms 27904 KB Output is correct
19 Correct 21 ms 27904 KB Output is correct
20 Correct 21 ms 27904 KB Output is correct
21 Correct 24 ms 28160 KB Output is correct
22 Incorrect 26 ms 31872 KB Output isn't correct
23 Incorrect 382 ms 48632 KB Output isn't correct
24 Incorrect 489 ms 52856 KB Output isn't correct
25 Correct 250 ms 46840 KB Output is correct
26 Correct 173 ms 41084 KB Output is correct
27 Correct 175 ms 40952 KB Output is correct
28 Correct 183 ms 41592 KB Output is correct
29 Correct 657 ms 78840 KB Output is correct
30 Incorrect 436 ms 52088 KB Output isn't correct
31 Incorrect 443 ms 52840 KB Output isn't correct
32 Incorrect 525 ms 52472 KB Output isn't correct
33 Correct 253 ms 48120 KB Output is correct
34 Correct 177 ms 40952 KB Output is correct
35 Correct 188 ms 40952 KB Output is correct
36 Correct 176 ms 41080 KB Output is correct
37 Correct 872 ms 91256 KB Output is correct
38 Incorrect 462 ms 52600 KB Output isn't correct
39 Incorrect 493 ms 52408 KB Output isn't correct
40 Incorrect 486 ms 52312 KB Output isn't correct
41 Correct 206 ms 47992 KB Output is correct
42 Correct 180 ms 41080 KB Output is correct
43 Correct 171 ms 41080 KB Output is correct
44 Correct 176 ms 40696 KB Output is correct
45 Correct 761 ms 83896 KB Output is correct
46 Incorrect 464 ms 52704 KB Output isn't correct
47 Incorrect 459 ms 52600 KB Output isn't correct
48 Incorrect 449 ms 52600 KB Output isn't correct
49 Correct 291 ms 46844 KB Output is correct
50 Correct 177 ms 41080 KB Output is correct
51 Correct 172 ms 41080 KB Output is correct
52 Correct 174 ms 40824 KB Output is correct
53 Correct 744 ms 84856 KB Output is correct
54 Incorrect 451 ms 52216 KB Output isn't correct