Submission #699695

#	Time	Username	Problem	Language	Result	Execution time	Memory
699695		finn__	Pipes (BOI13_pipes)	C++17	90.93 / 100	105 ms	14060 KiB

pipes

#include <bits/stdc++.h>
using namespace std;

#define N 100000
#define M 500000

vector<pair<unsigned, unsigned>> g[N];
int64_t y[N], ans[M];
bitset<N> visited;

int64_t solve_for_tree(unsigned u, unsigned p1 = -1, unsigned p2 = -1)
{
    int64_t val = 0;

    for (auto const &[v, i] : g[u])
        if (v != p1 && v != p2)
        {
            int64_t z = solve_for_tree(v, u);
            ans[i] = y[v] - z;
            val += ans[i];
        }

    return val;
}

unsigned find_cycle(unsigned u, vector<unsigned> &cycle, unsigned p = -1)
{
    if (visited[u])
        return u;
    visited[u] = 1;
    for (auto const &[v, i] : g[u])
        if (v != p)
        {
            unsigned x = find_cycle(v, cycle, u);
            if (x != UINT_MAX)
            {
                cycle.push_back(u);
                return x == u ? UINT_MAX : x;
            }
        }
    return UINT_MAX;
}

int main()
{
    size_t n, m;
    scanf("%zu %zu", &n, &m);

    if (m > n)
    {
        printf("0\n");
        return 0;
    }

    for (size_t i = 0; i < n; i++)
        scanf("%" PRId64, y + i);
    for (size_t i = 0; i < m; i++)
    {
        unsigned u, v;
        scanf("%u %u", &u, &v);
        g[u - 1].emplace_back(v - 1, i);
        g[v - 1].emplace_back(u - 1, i);
    }

    if (m + 1 == n)
        solve_for_tree(0);
    else
    {
        vector<unsigned> cycle;
        find_cycle(0, cycle);
        vector<int64_t> ny(cycle.size());
        for (size_t i = 0; i < cycle.size(); i++)
            ny[i] = y[cycle[i]] - solve_for_tree(cycle[i], cycle[(i + 1) % cycle.size()], cycle[(i - 1 + cycle.size()) % cycle.size()]);

        unsigned k;
        for (auto const &[v, i] : g[cycle[0]])
            if (v == cycle[1])
            {
                k = i;
                break;
            }

        g[cycle[0]].erase(find(g[cycle[0]].begin(), g[cycle[0]].end(), make_pair(cycle[1], k)));
        g[cycle[1]].erase(find(g[cycle[1]].begin(), g[cycle[1]].end(), make_pair(cycle[0], k)));

        for (size_t z = 0; z < 2; z++)
        {
            ans[k] = 0;
            for (size_t i = 0; i < cycle.size(); i++)
                ans[k] += ny[(i + z) % cycle.size()] * ((i & 1) ? -1 : 1);
            assert(!(ans[k] & 1));
            ans[k] >>= 1;

            y[cycle[0]] -= ans[k];
            y[cycle[1]] -= ans[k];

            if (!solve_for_tree(0))
                break;

            y[cycle[0]] += ans[k];
            y[cycle[1]] += ans[k];
        }
    }

    for (size_t i = 0; i < m; i++)
        printf("%" PRId64 "\n", 2 * ans[i]);
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%zu %zu", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
pipes.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%" PRId64, y + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
pipes.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%u %u", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:75:18: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |         unsigned k;
      |                  ^

• Subtask 1: 30 / 30
• Subtask 2: 60.925925925925924 / 70