oj.uz

Submission #83263

# Submission time Handle Problem Language Result Execution time Memory
83263 2018-11-06T12:56:34 Z teomrn Pipes (BOI13_pipes) C++14
0 / 100
 1000 ms 18140 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]) {
                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:55: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 2836 KB Output isn't correct
3 Incorrect 5 ms 2932 KB Output isn't correct
4 Incorrect 93 ms 8128 KB Output isn't correct
5 Incorrect 4 ms 8128 KB Output isn't correct
6 Incorrect 4 ms 8128 KB Output isn't correct
7 Incorrect 4 ms 8128 KB Output isn't correct
8 Incorrect 5 ms 8128 KB Output isn't correct
9 Incorrect 4 ms 8128 KB Output isn't correct
10 Incorrect 5 ms 8128 KB Output isn't correct
11 Incorrect 4 ms 8128 KB Output isn't correct
12 Incorrect 4 ms 8128 KB Output isn't correct
13 Incorrect 49 ms 8128 KB Output isn't correct
14 Incorrect 83 ms 8128 KB Output isn't correct
15 Incorrect 72 ms 8172 KB Output isn't correct
16 Incorrect 59 ms 8172 KB Output isn't correct
17 Incorrect 70 ms 8180 KB Output isn't correct
18 Incorrect 74 ms 8316 KB Output isn't correct
19 Incorrect 84 ms 13040 KB Output isn't correct
20 Incorrect 4 ms 13040 KB Output isn't correct
21 Incorrect 4 ms 13040 KB Output isn't correct
22 Incorrect 77 ms 13040 KB Output isn't correct
23 Incorrect 54 ms 13040 KB Output isn't correct
24 Incorrect 96 ms 13040 KB Output isn't correct
25 Incorrect 70 ms 13040 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 13040 KB Time limit exceeded
2 Execution timed out 1083 ms 13040 KB Time limit exceeded
3 Execution timed out 1075 ms 13040 KB Time limit exceeded
4 Execution timed out 1073 ms 16124 KB Time limit exceeded
5 Execution timed out 1079 ms 16124 KB Time limit exceeded
6 Execution timed out 1076 ms 18016 KB Time limit exceeded
7 Execution timed out 1063 ms 18016 KB Time limit exceeded
8 Execution timed out 1074 ms 18016 KB Time limit exceeded
9 Execution timed out 1080 ms 18016 KB Time limit exceeded
10 Execution timed out 1069 ms 18016 KB Time limit exceeded
11 Execution timed out 1073 ms 18016 KB Time limit exceeded
12 Execution timed out 1076 ms 18016 KB Time limit exceeded
13 Execution timed out 1066 ms 18016 KB Time limit exceeded
14 Execution timed out 1081 ms 18016 KB Time limit exceeded
15 Execution timed out 1064 ms 18016 KB Time limit exceeded
16 Execution timed out 1080 ms 18016 KB Time limit exceeded
17 Execution timed out 1078 ms 18016 KB Time limit exceeded
18 Execution timed out 1079 ms 18016 KB Time limit exceeded
19 Execution timed out 1093 ms 18016 KB Time limit exceeded
20 Execution timed out 1079 ms 18016 KB Time limit exceeded
21 Execution timed out 1084 ms 18016 KB Time limit exceeded
22 Execution timed out 1084 ms 18016 KB Time limit exceeded
23 Execution timed out 1078 ms 18016 KB Time limit exceeded
24 Execution timed out 1082 ms 18016 KB Time limit exceeded
25 Execution timed out 1049 ms 18016 KB Time limit exceeded
26 Execution timed out 1069 ms 18016 KB Time limit exceeded
27 Execution timed out 1065 ms 18016 KB Time limit exceeded
28 Execution timed out 1072 ms 18016 KB Time limit exceeded
29 Execution timed out 1072 ms 18016 KB Time limit exceeded
30 Execution timed out 1078 ms 18016 KB Time limit exceeded
31 Execution timed out 1074 ms 18016 KB Time limit exceeded
32 Execution timed out 1061 ms 18016 KB Time limit exceeded
33 Execution timed out 1081 ms 18016 KB Time limit exceeded
34 Execution timed out 1084 ms 18016 KB Time limit exceeded
35 Execution timed out 1075 ms 18016 KB Time limit exceeded
36 Execution timed out 1069 ms 18016 KB Time limit exceeded
37 Execution timed out 1076 ms 18016 KB Time limit exceeded
38 Execution timed out 1063 ms 18016 KB Time limit exceeded
39 Execution timed out 1050 ms 18016 KB Time limit exceeded
40 Execution timed out 1064 ms 18016 KB Time limit exceeded
41 Execution timed out 1068 ms 18016 KB Time limit exceeded
42 Execution timed out 1074 ms 18016 KB Time limit exceeded
43 Execution timed out 1061 ms 18016 KB Time limit exceeded
44 Execution timed out 1078 ms 18016 KB Time limit exceeded
45 Execution timed out 1077 ms 18016 KB Time limit exceeded
46 Execution timed out 1045 ms 18140 KB Time limit exceeded
47 Execution timed out 1075 ms 18140 KB Time limit exceeded
48 Execution timed out 1072 ms 18140 KB Time limit exceeded
49 Execution timed out 1052 ms 18140 KB Time limit exceeded
50 Execution timed out 1067 ms 18140 KB Time limit exceeded
51 Execution timed out 1059 ms 18140 KB Time limit exceeded
52 Execution timed out 1072 ms 18140 KB Time limit exceeded
53 Execution timed out 1066 ms 18140 KB Time limit exceeded
54 Execution timed out 1057 ms 18140 KB Time limit exceeded