oj.uz

답안 #699689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699689 2023-02-17T19:14:59 Z finn__ Pipes (BOI13_pipes) C++17
65 / 100
 96 ms 15628 KB 
#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] = 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;
            }
        for (size_t i = 0; i < cycle.size(); i++)
            ans[k] += ny[i] * ((i & 1) ? -1 : 1);
        ans[k] >>= 1;

        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)));
        y[cycle[0]] -= ans[k];
        y[cycle[1]] -= ans[k];

        solve_for_tree(0);
    }

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

Compilation message

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:84:16: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |         ans[k] >>= 1;
      |         ~~~~~~~^~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 57 ms 9872 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2660 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 52 ms 8460 KB Output is correct
14 Correct 55 ms 9512 KB Output is correct
15 Correct 61 ms 9896 KB Output is correct
16 Correct 48 ms 8784 KB Output is correct
17 Correct 57 ms 9884 KB Output is correct
18 Correct 67 ms 9880 KB Output is correct
19 Correct 70 ms 12480 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 59 ms 9912 KB Output is correct
23 Correct 47 ms 8348 KB Output is correct
24 Correct 60 ms 9908 KB Output is correct
25 Correct 48 ms 8692 KB Output is correct

Subtask #2
35.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Incorrect 2 ms 2792 KB Output isn't correct
3 Incorrect 71 ms 12252 KB Output isn't correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Incorrect 2 ms 2632 KB Output isn't correct
8 Incorrect 2 ms 2660 KB Output isn't correct
9 Incorrect 2 ms 2644 KB Output isn't correct
10 Correct 2 ms 2656 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Incorrect 2 ms 2644 KB Output isn't correct
15 Incorrect 2 ms 2772 KB Output isn't correct
16 Incorrect 2 ms 2668 KB Output isn't correct
17 Incorrect 2 ms 2772 KB Output isn't correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2668 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Incorrect 2 ms 2644 KB Output isn't correct
23 Incorrect 54 ms 11848 KB Output isn't correct
24 Incorrect 85 ms 13188 KB Output isn't correct
25 Incorrect 73 ms 12348 KB Output isn't correct
26 Correct 1 ms 2644 KB Output is correct
27 Correct 2 ms 2664 KB Output is correct
28 Correct 1 ms 2644 KB Output is correct
29 Correct 1 ms 2668 KB Output is correct
30 Incorrect 77 ms 14976 KB Output isn't correct
31 Incorrect 77 ms 15560 KB Output isn't correct
32 Incorrect 75 ms 11132 KB Output isn't correct
33 Incorrect 69 ms 13392 KB Output isn't correct
34 Correct 2 ms 2644 KB Output is correct
35 Correct 2 ms 2644 KB Output is correct
36 Correct 2 ms 2644 KB Output is correct
37 Correct 1 ms 2644 KB Output is correct
38 Incorrect 79 ms 14232 KB Output isn't correct
39 Incorrect 65 ms 10652 KB Output isn't correct
40 Incorrect 68 ms 12872 KB Output isn't correct
41 Incorrect 74 ms 15628 KB Output isn't correct
42 Correct 2 ms 2644 KB Output is correct
43 Correct 1 ms 2644 KB Output is correct
44 Correct 2 ms 2644 KB Output is correct
45 Correct 2 ms 2668 KB Output is correct
46 Incorrect 80 ms 15548 KB Output isn't correct
47 Incorrect 78 ms 13004 KB Output isn't correct
48 Incorrect 76 ms 15376 KB Output isn't correct
49 Incorrect 60 ms 10508 KB Output isn't correct
50 Correct 1 ms 2668 KB Output is correct
51 Correct 3 ms 2644 KB Output is correct
52 Correct 3 ms 2644 KB Output is correct
53 Correct 2 ms 2644 KB Output is correct
54 Incorrect 96 ms 13860 KB Output isn't correct