oj.uz

Submission #710799

# Submission time Handle Problem Language Result Execution time Memory
710799 2023-03-15T20:33:28 Z pls33 Pipes (BOI13_pipes) C++17
74.0741 / 100
 202 ms 21688 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];
            initial[next] -= initial[cur];
            degree[next]--;

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

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

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)
    {
        q.push((int)distance(degree.begin(), it));
        check_leaves(q, checked, fill, initial, degree, adj);
    }

    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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 52 ms 8908 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 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 2 ms 340 KB Output is correct
13 Correct 60 ms 7212 KB Output is correct
14 Correct 53 ms 8396 KB Output is correct
15 Correct 56 ms 9012 KB Output is correct
16 Correct 47 ms 7636 KB Output is correct
17 Correct 63 ms 8936 KB Output is correct
18 Correct 68 ms 8976 KB Output is correct
19 Correct 51 ms 8232 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 53 ms 9016 KB Output is correct
23 Correct 45 ms 7144 KB Output is correct
24 Correct 53 ms 8912 KB Output is correct
25 Correct 45 ms 7520 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Correct 38 ms 7756 KB Output is correct
4 Correct 39 ms 7968 KB Output is correct
5 Correct 42 ms 8136 KB Output is correct
6 Correct 202 ms 21688 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Incorrect 1 ms 212 KB Output isn't correct
15 Incorrect 1 ms 340 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 2 ms 468 KB Output is correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Incorrect 63 ms 6928 KB Output isn't correct
24 Incorrect 66 ms 8540 KB Output isn't correct
25 Correct 43 ms 7796 KB Output is correct
26 Correct 42 ms 7992 KB Output is correct
27 Correct 50 ms 7700 KB Output is correct
28 Correct 62 ms 8356 KB Output is correct
29 Correct 163 ms 18136 KB Output is correct
30 Incorrect 60 ms 8020 KB Output isn't correct
31 Incorrect 61 ms 8252 KB Output isn't correct
32 Incorrect 69 ms 8872 KB Output isn't correct
33 Correct 65 ms 8136 KB Output is correct
34 Correct 50 ms 7908 KB Output is correct
35 Correct 50 ms 8028 KB Output is correct
36 Correct 42 ms 8296 KB Output is correct
37 Correct 149 ms 21584 KB Output is correct
38 Incorrect 58 ms 8312 KB Output isn't correct
39 Incorrect 49 ms 8752 KB Output isn't correct
40 Incorrect 57 ms 8576 KB Output isn't correct
41 Correct 41 ms 7940 KB Output is correct
42 Correct 34 ms 7756 KB Output is correct
43 Correct 38 ms 7784 KB Output is correct
44 Correct 43 ms 8092 KB Output is correct
45 Correct 136 ms 17896 KB Output is correct
46 Incorrect 55 ms 8116 KB Output isn't correct
47 Incorrect 56 ms 8520 KB Output isn't correct
48 Incorrect 51 ms 8268 KB Output isn't correct
49 Correct 41 ms 7984 KB Output is correct
50 Correct 38 ms 7980 KB Output is correct
51 Correct 51 ms 8144 KB Output is correct
52 Correct 45 ms 7732 KB Output is correct
53 Correct 135 ms 18276 KB Output is correct
54 Incorrect 49 ms 8308 KB Output isn't correct