oj.uz

Submission #710822

# Submission time Handle Problem Language Result Execution time Memory
710822 2023-03-15T21:12:49 Z pls33 Pipes (BOI13_pipes) C++17
74.0741 / 100
 163 ms 21852 KB 
// boi2013 d1p3
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion

using state_t = bitset<(int)1e5>;

void check_leaves(queue<int> &q, state_t &checked,
                  vi64 &fill, vi64 &initial,
                  vi32 &degree, vvp32 &adj)
{
    while (!q.empty())
    {
        int cur = q.front();
        checked[cur] = true;
        q.pop();

        for (auto &[next, edge] : adj[cur])
        {
            if (checked[next])
            {
                continue;
            }
            fill[edge] += initial[cur] * 2;
            initial[next] -= initial[cur];
            degree[next]--;

            if (degree[next] == 1)
            {
                q.push(next);
            }
        }

        degree[cur] = max(0, degree[cur] - 1);
    }
}

void get_sum(int v, int64_t &sum, int &count, vvp32 &adj, state_t &checked, vi64 &initial)
{
    if (checked[v])
    {
        return;
    }

    sum += (count % 2) ? -initial[v] : initial[v];
    count++;
    checked[v] = true;
    for (auto &[next, edge] : adj[v])
    {
        if (checked[next])
        {
            continue;
        }

        get_sum(v, sum, count, adj, checked, initial);
    }
}

void check_cycle(int v, int64_t prev, int64_t &cur,
                 vvp32 &adj, state_t &checked,
                 vi64 &initial, vi64 &fill)
{
    if (checked[v])
    {
        return;
    }
    checked[v] = true;

    cur = initial[v] - prev;
    for (auto &[next, edge] : adj[v])
    {
        if (checked[next])
        {
            continue;
        }

        check_cycle(next, cur, fill[edge], adj, checked, initial, fill);
    }
}

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("pipes.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int v, e;
    cin >> v >> e;

    vi64 initial(v);
    for (auto &i : initial)
    {
        cin >> i;
    }

    vvp32 adj(v);
    vi32 degree(v);
    for (int i = 0; i < e; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
        degree[a]++;
        degree[b]++;
    }

    // kadangi jungus grafas, pirma atmetam visas medzio dalis ir po to jei lieka
    // nelyginis ciklas (is 2k+1 virsuniu), tai sutvarkom ji
    // jei lieka kazkoks keistas darinys, tai isvedam 0

    queue<int> q;
    for (int i = 0; i < v; i++)
    {
        if (degree[i] == 1)
        {
            q.push(i);
        }
    }

    state_t checked;
    vi64 fill(e);
    check_leaves(q, checked, fill, initial, degree, adj);

    auto it = max_element(degree.begin(), degree.end());
    if (*it > 2 || (v - checked.count() && !((v - checked.count()) % 2)))
    {
        cout << "0\n";
        return 0;
    }

    if (*it == 2)
    {
        checked.reset();
        for (int i = 0; i < v; i++)
        {
            checked[i] = degree[i] < 2;
        }

        state_t for_check = checked;
        int64_t sum = 0;
        int count = 0;
        int start = (int)distance(degree.begin(), it);
        get_sum(start, sum, count, adj, checked, initial);
        sum /= 2;

        checked = for_check;
        int id = 0;
        for (auto &[next, edge] : adj[start])
        {
            if (!checked[next])
            {
                id = edge;
                break;
            }
        }

        check_cycle(start, sum, fill[id], adj, checked, initial, fill);
    }

    for (auto &f : fill)
    {
        cout << f << '\n';
    }

    return 0;
}

Compilation message

pipes.cpp:9: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    9 | #pragma region dalykai
      | 
pipes.cpp:33: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   33 | #pragma endregion
      |

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 62 ms 9168 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 58 ms 7372 KB Output is correct
14 Correct 56 ms 8708 KB Output is correct
15 Correct 56 ms 9188 KB Output is correct
16 Correct 52 ms 7888 KB Output is correct
17 Correct 55 ms 9252 KB Output is correct
18 Correct 61 ms 9216 KB Output is correct
19 Correct 59 ms 8480 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 67 ms 9288 KB Output is correct
23 Correct 57 ms 7372 KB Output is correct
24 Correct 66 ms 9176 KB Output is correct
25 Correct 43 ms 7724 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Correct 43 ms 8084 KB Output is correct
4 Correct 46 ms 8180 KB Output is correct
5 Correct 55 ms 8472 KB Output is correct
6 Correct 150 ms 21852 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Incorrect 1 ms 468 KB Output isn't correct
16 Incorrect 2 ms 340 KB Output isn't correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Incorrect 1 ms 468 KB Output isn't correct
23 Incorrect 58 ms 12064 KB Output isn't correct
24 Incorrect 81 ms 13732 KB Output isn't correct
25 Correct 45 ms 8064 KB Output is correct
26 Correct 40 ms 8268 KB Output is correct
27 Correct 44 ms 8040 KB Output is correct
28 Correct 45 ms 8652 KB Output is correct
29 Correct 160 ms 18468 KB Output is correct
30 Incorrect 86 ms 12512 KB Output isn't correct
31 Incorrect 85 ms 16716 KB Output isn't correct
32 Incorrect 69 ms 10656 KB Output isn't correct
33 Correct 52 ms 8376 KB Output is correct
34 Correct 48 ms 8076 KB Output is correct
35 Correct 49 ms 8160 KB Output is correct
36 Correct 62 ms 8524 KB Output is correct
37 Correct 163 ms 21812 KB Output is correct
38 Incorrect 58 ms 12916 KB Output isn't correct
39 Incorrect 67 ms 10236 KB Output isn't correct
40 Incorrect 75 ms 13416 KB Output isn't correct
41 Correct 49 ms 8112 KB Output is correct
42 Correct 38 ms 8172 KB Output is correct
43 Correct 37 ms 7940 KB Output is correct
44 Correct 43 ms 8376 KB Output is correct
45 Correct 155 ms 18216 KB Output is correct
46 Incorrect 61 ms 12188 KB Output isn't correct
47 Incorrect 66 ms 13456 KB Output isn't correct
48 Incorrect 66 ms 16460 KB Output isn't correct
49 Correct 48 ms 8272 KB Output is correct
50 Correct 45 ms 8224 KB Output is correct
51 Correct 43 ms 8424 KB Output is correct
52 Correct 40 ms 8012 KB Output is correct
53 Correct 137 ms 18712 KB Output is correct
54 Incorrect 86 ms 11996 KB Output isn't correct