oj.uz

Submission #278672

# Submission time Handle Problem Language Result Execution time Memory
278672 2020-08-21T16:17:36 Z HynDuf Pipes (BOI13_pipes) C++14
74.0741 / 100
 254 ms 23932 KB 
#include <bits/stdc++.h>

#define task "P"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 1e5 + 2;
int n, m, c[N], dep[N], deg[N], ans[5 * N];
vii g[N];
bool dfs(int u, int p)
{
    dep[u] = dep[p] + 1;
    for (ii v : g[u]) if (v.F != p && dep[v.F] && (dep[u] - dep[v.F]) % 2 == 1) return 1;
    for (ii v : g[u]) if (v.F != p && !dep[v.F] && dfs(v.F, u)) return 1;
    return 0;
}
int main()
{
#ifdef HynDuf
    freopen(task".in", "r", stdin);
    //freopen(task".out", "w", stdout);
#else
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    cin >> n >> m;
    rep(i, 1, n)
    {
        cin >> c[i];
        c[i] <<= 1;
    }
    rep(i, 1, m)
    {
        int u, v;
        cin >> u >> v;
        g[u].eb(v, i);
        g[v].eb(u, i);
        deg[u]++;
        deg[v]++;
    }
    if (dfs(1, 0))
    {
        cout << 0;
        return 0;
    }
    vi st;
    rep(i, 1, n) if (deg[i] == 1) st.pb(i);
    while (!st.empty())
    {
        int u = st.back();
        st.pop_back();
        deg[u]--;
        for (ii v : g[u]) if (deg[v.F] >= 1 && !ans[v.S])
        {
            ans[v.S] = c[u];
            c[v.F] -= c[u];
            if (--deg[v.F] == 1) st.pb(v.F);
        }
    }
    rep(i, 1, n) if (deg[i] > 2)
    {
        cout << 0;
        return 0;
    }
    rep(i, 1, n) if (deg[i] == 2)
    {
        int u = i, lst = 0, cnt = 0;
        ll sum = 0;
        while (1)
        {
            for (ii v : g[u]) if (deg[v.F] == 2 && v.F != lst)
            {
                cnt++;
                if (cnt & 1) sum += c[u];
                else sum -= c[u];
                lst = u;
                u = v.F;
                break;
            }
            if (u == i) break;
        }
        ll lstc = sum;
        u = i, lst = 0;
        while (1)
        {
            for (ii v : g[u]) if (deg[v.F] == 2 && v.F != lst)
            {
                ans[v.S] = c[u] - lstc;
                lstc = ans[v.S];
                lst = u;
                u = v.F;
                break;
            }
            if (u == i) break;
        }
        break;
    }
    rep(i, 1, m) cout << ans[i] << '\n';
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 81 ms 10328 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 3 ms 2816 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 2 ms 2816 KB Output is correct
13 Correct 58 ms 8820 KB Output is correct
14 Correct 73 ms 9972 KB Output is correct
15 Correct 83 ms 10312 KB Output is correct
16 Correct 76 ms 9396 KB Output is correct
17 Correct 105 ms 10324 KB Output is correct
18 Correct 91 ms 10356 KB Output is correct
19 Correct 95 ms 11768 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 3 ms 2816 KB Output is correct
22 Correct 102 ms 10356 KB Output is correct
23 Correct 65 ms 8820 KB Output is correct
24 Correct 86 ms 10356 KB Output is correct
25 Correct 69 ms 9076 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Incorrect 3 ms 2816 KB Output isn't correct
3 Correct 54 ms 10616 KB Output is correct
4 Correct 66 ms 12792 KB Output is correct
5 Correct 64 ms 9588 KB Output is correct
6 Correct 217 ms 23932 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Incorrect 2 ms 2688 KB Output isn't correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 3 ms 2688 KB Output is correct
14 Incorrect 2 ms 2688 KB Output isn't correct
15 Incorrect 2 ms 2816 KB Output isn't correct
16 Incorrect 2 ms 2816 KB Output isn't correct
17 Correct 2 ms 2816 KB Output is correct
18 Correct 2 ms 2816 KB Output is correct
19 Correct 2 ms 2816 KB Output is correct
20 Correct 2 ms 2816 KB Output is correct
21 Correct 3 ms 2816 KB Output is correct
22 Incorrect 2 ms 2816 KB Output isn't correct
23 Incorrect 83 ms 10856 KB Output isn't correct
24 Incorrect 84 ms 12460 KB Output isn't correct
25 Correct 53 ms 10616 KB Output is correct
26 Correct 65 ms 12412 KB Output is correct
27 Correct 61 ms 12536 KB Output is correct
28 Correct 82 ms 9812 KB Output is correct
29 Correct 174 ms 19916 KB Output is correct
30 Incorrect 83 ms 13432 KB Output isn't correct
31 Incorrect 88 ms 13688 KB Output isn't correct
32 Incorrect 81 ms 11124 KB Output isn't correct
33 Correct 56 ms 11384 KB Output is correct
34 Correct 63 ms 11896 KB Output is correct
35 Correct 67 ms 12792 KB Output is correct
36 Correct 63 ms 9592 KB Output is correct
37 Correct 254 ms 23672 KB Output is correct
38 Incorrect 100 ms 13176 KB Output isn't correct
39 Incorrect 92 ms 10740 KB Output isn't correct
40 Incorrect 96 ms 12280 KB Output isn't correct
41 Correct 73 ms 12896 KB Output is correct
42 Correct 78 ms 11896 KB Output is correct
43 Correct 71 ms 12792 KB Output is correct
44 Correct 73 ms 9588 KB Output is correct
45 Correct 188 ms 20664 KB Output is correct
46 Incorrect 103 ms 13944 KB Output isn't correct
47 Incorrect 98 ms 12280 KB Output isn't correct
48 Incorrect 107 ms 13560 KB Output isn't correct
49 Correct 57 ms 9456 KB Output is correct
50 Correct 79 ms 12112 KB Output is correct
51 Correct 68 ms 11128 KB Output is correct
52 Correct 68 ms 10360 KB Output is correct
53 Correct 173 ms 20856 KB Output is correct
54 Incorrect 84 ms 12792 KB Output isn't correct