oj.uz

Submission #710825

# Submission time Handle Problem Language Result Execution time Memory
710825 2023-03-15T21:27:26 Z pls33 Pipes (BOI13_pipes) C++17
67.5926 / 100
 160 ms 43692 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, state_t &edged,
                  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;
            }
            edged[edge] = true;
            fill[edge] += initial[cur];
            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,
             vp32 &thing)
{
    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;
        }

        thing.emplace_back(v, edge);

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

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, edged;
    vi64 fill(e);
    check_leaves(q, checked, edged, 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;
        }

        int64_t sum = 0;
        int count = 0;
        int start = (int)distance(degree.begin(), it);

        vp32 thing;
        get_sum(start, sum, count, adj, checked, initial, thing);
        sum /= 2;

        int64_t prev = sum;
        for (auto &[vertex, edge] : thing)
        {
            fill[edge] = initial[vertex] - prev;
            prev = fill[edge];
            edged[edge] = true;
        }

        for (int i = 0; i < e; i++)
        {
            if (!edged[i])
            {
                fill[i] = sum;
                break;
            }
        }
    }

    for (auto &f : fill)
    {
        cout << f * 2 << '\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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 55 ms 8992 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 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 340 KB Output is correct
13 Correct 45 ms 7224 KB Output is correct
14 Correct 48 ms 8508 KB Output is correct
15 Correct 55 ms 8996 KB Output is correct
16 Correct 42 ms 7620 KB Output is correct
17 Correct 56 ms 8944 KB Output is correct
18 Correct 53 ms 8988 KB Output is correct
19 Correct 55 ms 8244 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 53 ms 9008 KB Output is correct
23 Correct 39 ms 7116 KB Output is correct
24 Correct 53 ms 9040 KB Output is correct
25 Correct 47 ms 7564 KB Output is correct

Subtask #2
37.5925925926 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Correct 42 ms 7828 KB Output is correct
4 Correct 44 ms 7848 KB Output is correct
5 Correct 42 ms 8148 KB Output is correct
6 Runtime error 160 ms 43656 KB Execution killed with signal 11
7 Incorrect 0 ms 340 KB Output isn't correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 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 340 KB Output isn't correct
16 Incorrect 1 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 340 KB Output isn't correct
23 Incorrect 36 ms 6808 KB Output isn't correct
24 Incorrect 49 ms 8412 KB Output isn't correct
25 Correct 37 ms 7732 KB Output is correct
26 Correct 39 ms 7924 KB Output is correct
27 Correct 39 ms 7732 KB Output is correct
28 Runtime error 45 ms 8428 KB Execution killed with signal 6
29 Runtime error 141 ms 36860 KB Execution killed with signal 11
30 Incorrect 47 ms 8012 KB Output isn't correct
31 Incorrect 43 ms 8048 KB Output isn't correct
32 Incorrect 53 ms 8832 KB Output isn't correct
33 Correct 41 ms 8104 KB Output is correct
34 Correct 38 ms 7880 KB Output is correct
35 Correct 39 ms 7884 KB Output is correct
36 Runtime error 44 ms 8236 KB Execution killed with signal 6
37 Runtime error 157 ms 43692 KB Execution killed with signal 11
38 Incorrect 49 ms 8268 KB Output isn't correct
39 Incorrect 51 ms 8828 KB Output isn't correct
40 Incorrect 51 ms 8480 KB Output isn't correct
41 Correct 42 ms 7824 KB Output is correct
42 Correct 38 ms 7684 KB Output is correct
43 Correct 37 ms 7788 KB Output is correct
44 Correct 41 ms 8168 KB Output is correct
45 Correct 120 ms 18008 KB Output is correct
46 Incorrect 47 ms 8012 KB Output isn't correct
47 Incorrect 48 ms 8432 KB Output isn't correct
48 Incorrect 43 ms 8036 KB Output isn't correct
49 Correct 40 ms 8068 KB Output is correct
50 Correct 45 ms 8028 KB Output is correct
51 Correct 41 ms 8108 KB Output is correct
52 Correct 39 ms 7808 KB Output is correct
53 Correct 130 ms 18412 KB Output is correct
54 Incorrect 47 ms 8244 KB Output isn't correct