oj.uz

Submission #221953

# Submission time Handle Problem Language Result Execution time Memory
221953 2020-04-11T15:20:09 Z infinite_iq Pipes (BOI13_pipes) C++14
74.0741 / 100
 855 ms 97572 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 , sum , xxx ;
void dfs ( int node , int p ) {
        done [node] = 1;
        for ( auto u : v[node] ) {
                if ( u.fi == p ) C ;
                ll XXX = xxx ;
                if ( node != start ) XXX = -VAL[node];
                VAL[node] += XXX;
                VAL[u.fi] += XXX ;
                sum += XXX ;
                ret [ u.se ] = XXX ;
                if ( done[u.fi] ) C ;
                dfs ( u.fi , node ) ;
                break;
        }
}
int main () {
        mem ( ret , -1 ) ;
        cin >> n >> m ;
        for ( int i = 0 ; i < n ; i ++ ) cin >> val[i] , all += val[i];
        all /= 2 ;
        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 ] += ans [id] ;
                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 ) VAL[u.se] = val[u.se] ;
        start = s.begin()->se;
        xxx = 0 ;
        dfs(start,start);
        for ( auto u : s ) VAL[u.se] = val[u.se] ;
        xxx = all + sum ;
        xxx *= -1 ;
        mem(done,0);
        dfs(start,start);
        for ( int i = 0 ; i < m ;i ++ ) {
                if ( ret[i]!=-1 ) cout << ret[i]*2<<endl;
                else cout << -ans [i]*2 << endl;
        }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27776 KB Output is correct
2 Correct 22 ms 27776 KB Output is correct
3 Correct 24 ms 28032 KB Output is correct
4 Correct 515 ms 50040 KB Output is correct
5 Correct 21 ms 27776 KB Output is correct
6 Correct 21 ms 27776 KB Output is correct
7 Correct 22 ms 27776 KB Output is correct
8 Correct 21 ms 27776 KB Output is correct
9 Correct 24 ms 27904 KB Output is correct
10 Correct 24 ms 28024 KB Output is correct
11 Correct 25 ms 28032 KB Output is correct
12 Correct 27 ms 28152 KB Output is correct
13 Correct 414 ms 45432 KB Output is correct
14 Correct 491 ms 48888 KB Output is correct
15 Correct 521 ms 50168 KB Output is correct
16 Correct 465 ms 46844 KB Output is correct
17 Correct 515 ms 50040 KB Output is correct
18 Correct 534 ms 50072 KB Output is correct
19 Correct 485 ms 50168 KB Output is correct
20 Correct 21 ms 27776 KB Output is correct
21 Correct 24 ms 27904 KB Output is correct
22 Correct 562 ms 50212 KB Output is correct
23 Correct 413 ms 45396 KB Output is correct
24 Correct 527 ms 50296 KB Output is correct
25 Correct 445 ms 46456 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 31616 KB Output isn't correct
2 Incorrect 27 ms 31872 KB Output isn't correct
3 Correct 257 ms 48380 KB Output is correct
4 Correct 184 ms 42616 KB Output is correct
5 Correct 185 ms 42236 KB Output is correct
6 Correct 855 ms 97400 KB Output is correct
7 Incorrect 23 ms 31616 KB Output isn't correct
8 Incorrect 23 ms 31616 KB Output isn't correct
9 Correct 20 ms 27776 KB Output is correct
10 Correct 20 ms 27776 KB Output is correct
11 Correct 21 ms 27776 KB Output is correct
12 Correct 21 ms 27776 KB Output is correct
13 Correct 21 ms 27776 KB Output is correct
14 Incorrect 24 ms 31616 KB Output isn't correct
15 Incorrect 26 ms 31872 KB Output isn't correct
16 Incorrect 27 ms 31872 KB Output isn't correct
17 Correct 22 ms 27904 KB Output is correct
18 Correct 22 ms 27904 KB Output is correct
19 Correct 25 ms 28032 KB Output is correct
20 Correct 23 ms 27904 KB Output is correct
21 Correct 24 ms 28160 KB Output is correct
22 Incorrect 27 ms 31872 KB Output isn't correct
23 Incorrect 393 ms 50552 KB Output isn't correct
24 Incorrect 499 ms 54904 KB Output isn't correct
25 Correct 267 ms 48376 KB Output is correct
26 Correct 189 ms 42616 KB Output is correct
27 Correct 178 ms 42488 KB Output is correct
28 Correct 184 ms 43384 KB Output is correct
29 Correct 673 ms 83828 KB Output is correct
30 Incorrect 484 ms 54508 KB Output isn't correct
31 Incorrect 452 ms 54904 KB Output isn't correct
32 Incorrect 525 ms 54808 KB Output isn't correct
33 Correct 250 ms 49656 KB Output is correct
34 Correct 183 ms 42744 KB Output is correct
35 Correct 180 ms 42620 KB Output is correct
36 Correct 190 ms 42744 KB Output is correct
37 Correct 853 ms 97572 KB Output is correct
38 Incorrect 473 ms 55032 KB Output isn't correct
39 Incorrect 501 ms 54648 KB Output isn't correct
40 Incorrect 497 ms 54904 KB Output isn't correct
41 Correct 212 ms 49656 KB Output is correct
42 Correct 179 ms 42716 KB Output is correct
43 Correct 181 ms 42616 KB Output is correct
44 Correct 175 ms 42232 KB Output is correct
45 Correct 773 ms 88952 KB Output is correct
46 Incorrect 486 ms 55032 KB Output isn't correct
47 Incorrect 482 ms 54904 KB Output isn't correct
48 Incorrect 461 ms 55032 KB Output isn't correct
49 Correct 296 ms 48376 KB Output is correct
50 Correct 173 ms 42616 KB Output is correct
51 Correct 182 ms 42616 KB Output is correct
52 Correct 181 ms 42360 KB Output is correct
53 Correct 796 ms 90336 KB Output is correct
54 Incorrect 486 ms 54724 KB Output isn't correct