oj.uz

Submission #83264

# Submission time Handle Problem Language Result Execution time Memory
83264 2018-11-06T12:57:07 Z teomrn Pipes (BOI13_pipes) C++14
0 / 100
 1000 ms 22572 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
const int NMAX = 100010;

vector <pair <int, int>> adia[NMAX + 10];
int tata[NMAX + 10];
int taken[NMAX + 10];
int h[NMAX + 10];
bool ok = 1;
i64 ce_s_vrea[NMAX + 10];
int ans[5 * NMAX + 10];

vector <vector <int>> centers;

bool dfs(int nod, bool did)
{
    for (auto i : adia[nod]) {
        if (i.first == tata[nod])
            continue;
        if (tata[i.first] != 0) {
            if (h[i.first] > h[nod])
                continue;
            if (did) {
                ok = 0;
                return 1;
            }
            vector <int> c;
            for (int j = nod; j != tata[i.first]; j = tata[j]) {
                if (j == -1)
                    while (1);
                if (taken[j]) {
                    ok = 0;
                    return 1;
                }
                taken[j] = 1;
                c.push_back(j);
            }
            centers.push_back(c);
            did = 1;
        }
        else {
            tata[i.first] = nod;
            h[i.first] = 1 + h[nod];
            did |= dfs(i.first, did);
            if (!ok)
                return 1;
        }
    }
    return did;
}

int solve_arb(int nod, int tata)
{
    int ce_tata;
    for (auto i : adia[nod]) {
        if (i.first != tata) {
            ans[i.second] = solve_arb(i.first, nod);
            ce_s_vrea[nod] -= ans[i.second];
        }
    }
    return ce_s_vrea[nod];
}

void solve_ciclu(vector <int> ciclu)
{
    vector <int> a(ciclu.size());
    vector <i64> s_st(ciclu.size()), s_dr(ciclu.size());

    int n = ciclu.size();

    if (n % 2 == 0) {
        ok = 0;
        return;
    }

    for (int i = 0; i < n; i++) {
        for (auto j : adia[ciclu[i]]) {
            if (j.first != ciclu[(i + 1) % n] && j.first != ciclu[(i + n - 1) % n]) {
                int x = solve_arb(j.first, ciclu[i]);
                ce_s_vrea[ciclu[i]] -= x;
                ans[j.second] = x;
            }
            else if (j.first == ciclu[(i + n - 1) % n])
                a[i] = j.second;
        }
    }
    i64 s_total = 0;
    for (auto i : ciclu)
        s_total += ce_s_vrea[i];

    if ((s_total & 1LL) || (s_total && n == 1)) {
        ok = 0;
        return;
    }

    s_st[0] = ce_s_vrea[ciclu[0]];
    for (int i = 1; i < n; i++)
        s_st[i] = ce_s_vrea[ciclu[i]] - s_st[i - 1];
    s_dr[n - 1] = ce_s_vrea[ciclu[n - 1]];
    for (int i = n - 2; i >= 0; i--)
        s_dr[i] = ce_s_vrea[ciclu[i]] - s_dr[i + 1];

    for (int i = 0; i < n; i++)
        ans[a[i]] = (s_st[i] + s_dr[i] - ce_s_vrea[ciclu[i]]) / 2;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, a, b;

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

    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        adia[a].push_back({ b, i });
        adia[b].push_back({ a, i });
    }

    for (int i = 1; i <= n; i++) {
        if (!tata[i]) {
            tata[i] = -1;
            auto x = dfs(i, 0);
            if (!x)
            centers.push_back({ i });
        }
    }

    return 0;

    if (!ok) {
        cout << 0 << '\n';
        return 0;
    }

    for (auto i : centers)
        solve_ciclu(i);

    if (!ok) {
        cout << 0 << '\n';
        return 0;
    }

    for (int i = 1; i <= m; i++)
        cout << 2LL * ans[i] << '\n';

    return 0;
}

Compilation message

pipes.cpp: In function 'int solve_arb(int, int)':
pipes.cpp:56:9: warning: unused variable 'ce_tata' [-Wunused-variable]
     int ce_tata;
         ^~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Incorrect 4 ms 2808 KB Output isn't correct
3 Incorrect 4 ms 3016 KB Output isn't correct
4 Incorrect 69 ms 8672 KB Output isn't correct
5 Incorrect 4 ms 8672 KB Output isn't correct
6 Incorrect 4 ms 8672 KB Output isn't correct
7 Incorrect 4 ms 8672 KB Output isn't correct
8 Incorrect 4 ms 8672 KB Output isn't correct
9 Incorrect 5 ms 8672 KB Output isn't correct
10 Incorrect 4 ms 8672 KB Output isn't correct
11 Incorrect 6 ms 8672 KB Output isn't correct
12 Incorrect 4 ms 8672 KB Output isn't correct
13 Incorrect 63 ms 8672 KB Output isn't correct
14 Incorrect 67 ms 8672 KB Output isn't correct
15 Incorrect 71 ms 8736 KB Output isn't correct
16 Incorrect 67 ms 8736 KB Output isn't correct
17 Incorrect 69 ms 8736 KB Output isn't correct
18 Incorrect 71 ms 8796 KB Output isn't correct
19 Incorrect 79 ms 15152 KB Output isn't correct
20 Incorrect 4 ms 15152 KB Output isn't correct
21 Incorrect 4 ms 15152 KB Output isn't correct
22 Incorrect 70 ms 15152 KB Output isn't correct
23 Incorrect 56 ms 15152 KB Output isn't correct
24 Incorrect 72 ms 15152 KB Output isn't correct
25 Incorrect 60 ms 15152 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 15152 KB Output isn't correct
2 Incorrect 5 ms 15152 KB Output isn't correct
3 Incorrect 94 ms 15412 KB Output isn't correct
4 Execution timed out 1054 ms 19864 KB Time limit exceeded
5 Execution timed out 1075 ms 19864 KB Time limit exceeded
6 Execution timed out 1085 ms 19864 KB Time limit exceeded
7 Incorrect 4 ms 19864 KB Output isn't correct
8 Incorrect 4 ms 19864 KB Output isn't correct
9 Incorrect 5 ms 19864 KB Output isn't correct
10 Incorrect 4 ms 19864 KB Output isn't correct
11 Incorrect 4 ms 19864 KB Output isn't correct
12 Incorrect 4 ms 19864 KB Output isn't correct
13 Execution timed out 1069 ms 19864 KB Time limit exceeded
14 Incorrect 4 ms 19864 KB Output isn't correct
15 Incorrect 4 ms 19864 KB Output isn't correct
16 Incorrect 4 ms 19864 KB Output isn't correct
17 Incorrect 4 ms 19864 KB Output isn't correct
18 Execution timed out 1044 ms 19864 KB Time limit exceeded
19 Execution timed out 1082 ms 19864 KB Time limit exceeded
20 Execution timed out 1074 ms 19864 KB Time limit exceeded
21 Execution timed out 1067 ms 19864 KB Time limit exceeded
22 Incorrect 5 ms 19864 KB Output isn't correct
23 Incorrect 67 ms 19864 KB Output isn't correct
24 Incorrect 88 ms 19864 KB Output isn't correct
25 Incorrect 80 ms 19864 KB Output isn't correct
26 Execution timed out 1087 ms 19864 KB Time limit exceeded
27 Incorrect 105 ms 19864 KB Output isn't correct
28 Execution timed out 1066 ms 19864 KB Time limit exceeded
29 Execution timed out 1065 ms 19864 KB Time limit exceeded
30 Incorrect 127 ms 21292 KB Output isn't correct
31 Incorrect 98 ms 21836 KB Output isn't correct
32 Incorrect 75 ms 21836 KB Output isn't correct
33 Incorrect 81 ms 21836 KB Output isn't correct
34 Execution timed out 1074 ms 21836 KB Time limit exceeded
35 Execution timed out 1073 ms 21836 KB Time limit exceeded
36 Execution timed out 1069 ms 21836 KB Time limit exceeded
37 Execution timed out 1083 ms 21836 KB Time limit exceeded
38 Incorrect 91 ms 21836 KB Output isn't correct
39 Incorrect 69 ms 21836 KB Output isn't correct
40 Incorrect 73 ms 21836 KB Output isn't correct
41 Incorrect 82 ms 21836 KB Output isn't correct
42 Execution timed out 1056 ms 21836 KB Time limit exceeded
43 Incorrect 99 ms 21836 KB Output isn't correct
44 Execution timed out 1057 ms 21836 KB Time limit exceeded
45 Execution timed out 1073 ms 21836 KB Time limit exceeded
46 Incorrect 91 ms 22572 KB Output isn't correct
47 Incorrect 80 ms 22572 KB Output isn't correct
48 Incorrect 79 ms 22572 KB Output isn't correct
49 Incorrect 66 ms 22572 KB Output isn't correct
50 Execution timed out 1060 ms 22572 KB Time limit exceeded
51 Execution timed out 1078 ms 22572 KB Time limit exceeded
52 Execution timed out 1073 ms 22572 KB Time limit exceeded
53 Execution timed out 1071 ms 22572 KB Time limit exceeded
54 Incorrect 73 ms 22572 KB Output isn't correct