oj.uz

Submission #311581

# Submission time Handle Problem Language Result Execution time Memory
311581 2020-10-10T17:13:41 Z Hehehe Pipes (BOI13_pipes) C++14
100 / 100
 152 ms 85112 KB 
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
//#define int long long


const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e6;
const ll mod = 1e9 + 7;
const int N = 3e6 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

int n, m;
vector<pi> v[N];
ll val[N], vis[N], C[N], d[N], L = -1, R, ID = -1, bb, s;

void dfs(int nod, int p) {

    	ll cur = C[nod];
    	vis[nod] = 1;

    	if(d[nod] & 1) s -= C[nod];else s += C[nod];

    	for(auto i : v[nod]){
            int it = i.ff, id = i.ss;
            if(it == p)continue;
    		if(!vis[it]) {
    			d[it] = d[nod] + 1;
    			dfs(it, nod);
    		}else
    		if(d[it] < d[nod]) {
    			if(d[it] % 2 != d[nod] % 2){
                    cout << "0\n";
                    exit(0);
                }
    			L = it, R = nod, ID = id, bb = d[nod] & 1;
    		}
    	}
}

ll recover(int nod, int p) {
    ll cur = C[nod];
    for(auto i : v[nod]){
        int it = i.ff, id = i.ss;
        if(it == p || id == ID)continue;
        ll t = recover(it, nod);
        val[id] = t;
        cur += t;
    }
    return -cur;
}



void solve(){

    cin >> n >> m;

    if(m > n){
        cout << "0" << '\n';
        return;
    }

    for(int i = 1; i <= n; i++) cin >> C[i];

    for(int i = 0, x, y; i < m; i++) {
        cin >> x >> y;
        v[x].push_back({y, i});
        v[y].push_back({x, i});
    }

    dfs(1, 1);

    if(L != -1) {

        if(bb) s *= -1;
        C[L] -= s/2;
        C[R] -= s/2;
        val[ID] = (-s)/2;
    }

    recover(1, 1);

    for(int i = 0; i < m; i++) cout << -2ll*val[i] << '\n';
}

int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //cout << setprecision(6) << fixed;

    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}

Compilation message

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:33:9: warning: unused variable 'cur' [-Wunused-variable]
   33 |      ll cur = C[nod];
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 70776 KB Output is correct
2 Correct 46 ms 70776 KB Output is correct
3 Correct 48 ms 70904 KB Output is correct
4 Correct 124 ms 79608 KB Output is correct
5 Correct 48 ms 70908 KB Output is correct
6 Correct 47 ms 70776 KB Output is correct
7 Correct 47 ms 70776 KB Output is correct
8 Correct 49 ms 70776 KB Output is correct
9 Correct 49 ms 70904 KB Output is correct
10 Correct 48 ms 70904 KB Output is correct
11 Correct 48 ms 70904 KB Output is correct
12 Correct 47 ms 70904 KB Output is correct
13 Correct 113 ms 77816 KB Output is correct
14 Correct 125 ms 79224 KB Output is correct
15 Correct 127 ms 79864 KB Output is correct
16 Correct 112 ms 78328 KB Output is correct
17 Correct 125 ms 79608 KB Output is correct
18 Correct 126 ms 79736 KB Output is correct
19 Correct 139 ms 82168 KB Output is correct
20 Correct 46 ms 70784 KB Output is correct
21 Correct 47 ms 70904 KB Output is correct
22 Correct 127 ms 79796 KB Output is correct
23 Correct 109 ms 77816 KB Output is correct
24 Correct 126 ms 79864 KB Output is correct
25 Correct 113 ms 78200 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 70776 KB Output is correct
2 Correct 49 ms 70984 KB Output is correct
3 Correct 110 ms 79932 KB Output is correct
4 Correct 47 ms 70776 KB Output is correct
5 Correct 47 ms 70776 KB Output is correct
6 Correct 47 ms 70776 KB Output is correct
7 Correct 47 ms 70904 KB Output is correct
8 Correct 47 ms 70776 KB Output is correct
9 Correct 46 ms 70776 KB Output is correct
10 Correct 46 ms 70776 KB Output is correct
11 Correct 46 ms 70776 KB Output is correct
12 Correct 47 ms 70776 KB Output is correct
13 Correct 47 ms 70776 KB Output is correct
14 Correct 46 ms 70776 KB Output is correct
15 Correct 47 ms 70904 KB Output is correct
16 Correct 49 ms 70904 KB Output is correct
17 Correct 48 ms 70936 KB Output is correct
18 Correct 46 ms 70776 KB Output is correct
19 Correct 47 ms 70784 KB Output is correct
20 Correct 47 ms 70776 KB Output is correct
21 Correct 47 ms 70776 KB Output is correct
22 Correct 47 ms 70904 KB Output is correct
23 Correct 120 ms 81016 KB Output is correct
24 Correct 130 ms 82680 KB Output is correct
25 Correct 107 ms 79864 KB Output is correct
26 Correct 47 ms 70904 KB Output is correct
27 Correct 47 ms 70776 KB Output is correct
28 Correct 46 ms 70784 KB Output is correct
29 Correct 48 ms 70848 KB Output is correct
30 Correct 140 ms 84412 KB Output is correct
31 Correct 142 ms 84728 KB Output is correct
32 Correct 136 ms 80624 KB Output is correct
33 Correct 105 ms 80760 KB Output is correct
34 Correct 48 ms 70776 KB Output is correct
35 Correct 47 ms 70776 KB Output is correct
36 Correct 47 ms 70784 KB Output is correct
37 Correct 46 ms 70776 KB Output is correct
38 Correct 143 ms 83960 KB Output is correct
39 Correct 133 ms 80248 KB Output is correct
40 Correct 140 ms 82552 KB Output is correct
41 Correct 117 ms 82124 KB Output is correct
42 Correct 48 ms 70776 KB Output is correct
43 Correct 46 ms 70776 KB Output is correct
44 Correct 47 ms 70776 KB Output is correct
45 Correct 47 ms 70904 KB Output is correct
46 Correct 152 ms 85112 KB Output is correct
47 Correct 140 ms 82684 KB Output is correct
48 Correct 142 ms 84472 KB Output is correct
49 Correct 115 ms 78584 KB Output is correct
50 Correct 49 ms 70784 KB Output is correct
51 Correct 49 ms 70776 KB Output is correct
52 Correct 46 ms 70776 KB Output is correct
53 Correct 46 ms 70784 KB Output is correct
54 Correct 145 ms 83320 KB Output is correct