oj.uz

Submission #83267

# Submission time Handle Problem Language Result Execution time Memory
83267 2018-11-06T13:00:47 Z teomrn Pipes (BOI13_pipes) C++14
0 / 100
 1000 ms 22136 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 activ[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)
{
    activ[nod] = 1;
    for (auto i : adia[nod]) {
        if (i.first == tata[nod])
            continue;
        if (tata[i.first] != 0) {
            if (h[i.first] > h[nod])
                continue;
            assert(activ[i.first]);
            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;
        }
    }
    activ[nod] = 0;
    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:60:9: warning: unused variable 'ce_tata' [-Wunused-variable]
     int ce_tata;
         ^~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB Output isn't correct
2 Incorrect 4 ms 2804 KB Output isn't correct
3 Incorrect 4 ms 2880 KB Output isn't correct
4 Incorrect 74 ms 8280 KB Output isn't correct
5 Incorrect 4 ms 8280 KB Output isn't correct
6 Incorrect 4 ms 8280 KB Output isn't correct
7 Incorrect 4 ms 8280 KB Output isn't correct
8 Incorrect 5 ms 8280 KB Output isn't correct
9 Incorrect 4 ms 8280 KB Output isn't correct
10 Incorrect 6 ms 8280 KB Output isn't correct
11 Incorrect 5 ms 8280 KB Output isn't correct
12 Incorrect 4 ms 8280 KB Output isn't correct
13 Incorrect 57 ms 8280 KB Output isn't correct
14 Incorrect 81 ms 8280 KB Output isn't correct
15 Incorrect 76 ms 8316 KB Output isn't correct
16 Incorrect 66 ms 8316 KB Output isn't correct
17 Incorrect 74 ms 8316 KB Output isn't correct
18 Incorrect 82 ms 8316 KB Output isn't correct
19 Incorrect 84 ms 14716 KB Output isn't correct
20 Incorrect 5 ms 14716 KB Output isn't correct
21 Incorrect 4 ms 14716 KB Output isn't correct
22 Incorrect 93 ms 14716 KB Output isn't correct
23 Incorrect 50 ms 14716 KB Output isn't correct
24 Incorrect 69 ms 14716 KB Output isn't correct
25 Incorrect 64 ms 14716 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 14716 KB Output isn't correct
2 Incorrect 5 ms 14716 KB Output isn't correct
3 Incorrect 81 ms 14924 KB Output isn't correct
4 Execution timed out 1052 ms 19308 KB Time limit exceeded
5 Execution timed out 1060 ms 19308 KB Time limit exceeded
6 Execution timed out 1070 ms 19308 KB Time limit exceeded
7 Incorrect 4 ms 19308 KB Output isn't correct
8 Incorrect 4 ms 19308 KB Output isn't correct
9 Incorrect 4 ms 19308 KB Output isn't correct
10 Incorrect 5 ms 19308 KB Output isn't correct
11 Incorrect 4 ms 19308 KB Output isn't correct
12 Incorrect 4 ms 19308 KB Output isn't correct
13 Execution timed out 1068 ms 19308 KB Time limit exceeded
14 Incorrect 4 ms 19308 KB Output isn't correct
15 Incorrect 4 ms 19308 KB Output isn't correct
16 Incorrect 4 ms 19308 KB Output isn't correct
17 Incorrect 4 ms 19308 KB Output isn't correct
18 Execution timed out 1059 ms 19308 KB Time limit exceeded
19 Execution timed out 1072 ms 19308 KB Time limit exceeded
20 Execution timed out 1044 ms 19308 KB Time limit exceeded
21 Execution timed out 1069 ms 19308 KB Time limit exceeded
22 Incorrect 5 ms 19308 KB Output isn't correct
23 Incorrect 73 ms 19308 KB Output isn't correct
24 Incorrect 88 ms 19308 KB Output isn't correct
25 Incorrect 81 ms 19308 KB Output isn't correct
26 Execution timed out 1068 ms 19308 KB Time limit exceeded
27 Incorrect 90 ms 19308 KB Output isn't correct
28 Execution timed out 1060 ms 19308 KB Time limit exceeded
29 Execution timed out 1065 ms 19308 KB Time limit exceeded
30 Incorrect 106 ms 20856 KB Output isn't correct
31 Incorrect 117 ms 21336 KB Output isn't correct
32 Incorrect 81 ms 21336 KB Output isn't correct
33 Incorrect 90 ms 21336 KB Output isn't correct
34 Execution timed out 1075 ms 21336 KB Time limit exceeded
35 Execution timed out 1073 ms 21336 KB Time limit exceeded
36 Execution timed out 1069 ms 21336 KB Time limit exceeded
37 Execution timed out 1078 ms 21336 KB Time limit exceeded
38 Incorrect 123 ms 21336 KB Output isn't correct
39 Incorrect 74 ms 21336 KB Output isn't correct
40 Incorrect 89 ms 21336 KB Output isn't correct
41 Incorrect 110 ms 21368 KB Output isn't correct
42 Execution timed out 1084 ms 21368 KB Time limit exceeded
43 Incorrect 89 ms 21368 KB Output isn't correct
44 Execution timed out 1084 ms 21368 KB Time limit exceeded
45 Execution timed out 1075 ms 21368 KB Time limit exceeded
46 Incorrect 108 ms 22136 KB Output isn't correct
47 Incorrect 92 ms 22136 KB Output isn't correct
48 Incorrect 108 ms 22136 KB Output isn't correct
49 Incorrect 61 ms 22136 KB Output isn't correct
50 Execution timed out 1078 ms 22136 KB Time limit exceeded
51 Execution timed out 1087 ms 22136 KB Time limit exceeded
52 Execution timed out 1080 ms 22136 KB Time limit exceeded
53 Execution timed out 1064 ms 22136 KB Time limit exceeded
54 Incorrect 85 ms 22136 KB Output isn't correct