oj.uz

답안 #699696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699696 2023-02-17T19:41:46 Z finn__ Pipes (BOI13_pipes) C++17
70.1852 / 100
 101 ms 28232 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] = 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] & 3));
            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

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 54 ms 8352 KB Output is correct
5 Correct 1 ms 2660 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 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 2644 KB Output is correct
12 Correct 2 ms 2660 KB Output is correct
13 Correct 46 ms 7160 KB Output is correct
14 Correct 49 ms 8004 KB Output is correct
15 Correct 53 ms 8396 KB Output is correct
16 Correct 44 ms 7500 KB Output is correct
17 Correct 53 ms 8336 KB Output is correct
18 Correct 54 ms 8396 KB Output is correct
19 Correct 67 ms 11008 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 54 ms 8288 KB Output is correct
23 Correct 41 ms 7084 KB Output is correct
24 Correct 53 ms 8332 KB Output is correct
25 Correct 44 ms 7348 KB Output is correct

Subtask #2
40.1851851852 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 5204 KB Execution killed with signal 6
2 Correct 2 ms 2772 KB Output is correct
3 Incorrect 78 ms 10772 KB Output isn't correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Runtime error 4 ms 5204 KB Execution killed with signal 6
8 Runtime error 4 ms 5204 KB Execution killed with signal 6
9 Incorrect 2 ms 2644 KB Output isn't correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Runtime error 4 ms 5332 KB Execution killed with signal 6
17 Incorrect 2 ms 2644 KB Output isn't correct
18 Correct 1 ms 2644 KB Output is correct
19 Correct 1 ms 2648 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 1 ms 2644 KB Output is correct
22 Runtime error 5 ms 5460 KB Execution killed with signal 6
23 Runtime error 47 ms 21420 KB Execution killed with signal 6
24 Runtime error 67 ms 23516 KB Execution killed with signal 6
25 Incorrect 74 ms 10792 KB Output isn't correct
26 Correct 1 ms 2644 KB Output is correct
27 Correct 1 ms 2644 KB Output is correct
28 Correct 1 ms 2644 KB Output is correct
29 Correct 1 ms 2644 KB Output is correct
30 Correct 84 ms 13392 KB Output is correct
31 Runtime error 64 ms 28232 KB Execution killed with signal 6
32 Runtime error 55 ms 18492 KB Execution killed with signal 6
33 Incorrect 76 ms 11820 KB Output isn't correct
34 Correct 1 ms 2644 KB Output is correct
35 Correct 1 ms 2644 KB Output is correct
36 Correct 1 ms 2644 KB Output is correct
37 Correct 2 ms 2644 KB Output is correct
38 Runtime error 62 ms 22192 KB Execution killed with signal 6
39 Runtime error 57 ms 17488 KB Execution killed with signal 6
40 Runtime error 66 ms 22920 KB Execution killed with signal 6
41 Incorrect 101 ms 14152 KB Output isn't correct
42 Correct 1 ms 2648 KB Output is correct
43 Correct 1 ms 2644 KB Output is correct
44 Correct 1 ms 2644 KB Output is correct
45 Correct 1 ms 2644 KB Output is correct
46 Runtime error 78 ms 28076 KB Execution killed with signal 6
47 Runtime error 74 ms 23060 KB Execution killed with signal 6
48 Runtime error 64 ms 27844 KB Execution killed with signal 6
49 Incorrect 66 ms 8992 KB Output isn't correct
50 Correct 2 ms 2644 KB Output is correct
51 Correct 2 ms 2644 KB Output is correct
52 Correct 2 ms 2644 KB Output is correct
53 Correct 2 ms 2644 KB Output is correct
54 Runtime error 65 ms 24544 KB Execution killed with signal 6