Submission #710799

#	Time	Username	Problem	Language	Result	Execution time	Memory
710799		pls33	Pipes (BOI13_pipes)	C++17	74.07 / 100	202 ms	21688 KiB

pipes

// 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 (stderr)

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 / 30
• Subtask 2: 44.074074074074076 / 70