답안 #83255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83255	2018-11-06T12:18:15 Z	teomrn	Pipes (BOI13_pipes)	C++14	1.2963 / 100	419 ms	132096 KB

pipes

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

typedef long long i64;
const int NMAX = 100010;

vector <pair <int, int>> adia[NMAX + 10];
int tata[NMAX + 10];
int taken[NMAX + 10];
int h[NMAX + 10];
bool ok = 1;
i64 ce_s_vrea[NMAX + 10];
int ans[5 * NMAX + 10];

vector <vector <int>> centers;

bool dfs(int nod, bool did)
{
    for (auto i : adia[nod]) {
        if (i.first == tata[nod])
            continue;
        if (tata[i.first]) {
            if (h[i.first] > h[nod])
                continue;
            if (did) {
                ok = 0;
                return 1;
            }
            vector <int> c;
            for (int j = nod; j != tata[i.first]; j = tata[j]) {
                if (taken[j]) {
                    ok = 0;
                    return 1;
                }
                taken[j] = 1;
                c.push_back(j);
            }
            centers.push_back(c);
            did = 1;
        }
        else {
            tata[i.first] = nod;
            h[i.first] = 1 + h[nod];
            did |= dfs(i.first, did);
            if (!ok)
                return 1;
        }
    }
    return did;
}

int solve_arb(int nod, int tata)
{
    int ce_tata;
    for (auto i : adia[nod]) {
        if (i.first != tata) {
            ans[i.second] = solve_arb(i.first, nod);
            ce_s_vrea[nod] -= ans[i.second];
        }
    }
    return ce_s_vrea[nod];
}

void solve_ciclu(vector <int> ciclu)
{
    vector <int> a(ciclu.size());
    vector <i64> s_st(ciclu.size()), s_dr(ciclu.size());

    int n = ciclu.size();

    if (n % 2 == 0) {
        ok = 0;
        return;
    }

    for (int i = 0; i < n; i++) {
        for (auto j : adia[ciclu[i]]) {
            if (j.first != ciclu[(i + 1) % n] && j.first != ciclu[(i + n - 1) % n]) {
                int x = solve_arb(j.first, ciclu[i]);
                ce_s_vrea[ciclu[i]] -= x;
                ans[j.second] = x;
            }
            else if (j.first == ciclu[(i + n - 1) % n])
                a[i] = j.second;
        }
    }
    i64 s_total = 0;
    for (auto i : ciclu)
        s_total += ce_s_vrea[i];

    if ((s_total & 1LL) || (s_total && n == 1)) {
        ok = 0;
        return;
    }

    s_st[0] = ce_s_vrea[ciclu[0]];
    for (int i = 1; i < n; i++)
        s_st[i] = ce_s_vrea[ciclu[i]] - s_st[i - 1];
    s_dr[n - 1] = ce_s_vrea[ciclu[n - 1]];
    for (int i = n - 2; i >= 0; i--)
        s_dr[i] = ce_s_vrea[ciclu[i]] - s_dr[i + 1];

    for (int i = 0; i < n; i++)
        ans[a[i]] = (s_st[i] + s_dr[i] - ce_s_vrea[ciclu[i]]) / 2;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, a, b;

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> ce_s_vrea[i];

    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        adia[a].push_back({ b, i });
        adia[b].push_back({ a, i });
    }

    for (int i = 1; i <= n; i++) {
        if (!tata[i]) {
            tata[i] = -1;
            auto x = dfs(i, 0);
            if (!x)
            centers.push_back({ i });
        }
    }

    for (auto i : centers)
        solve_ciclu(i);



    if (!ok) {
        cout << 0 << '\n';
        return 0;
    }

    for (int i = 1; i <= m; i++)
        cout << ans[i] << '\n';

    return 0;
}

Compilation message

pipes.cpp: In function 'int solve_arb(int, int)':
pipes.cpp:54:9: warning: unused variable 'ce_tata' [-Wunused-variable]
     int ce_tata;
         ^~~~~~~

Subtask #1

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	2812 KB	Output isn't correct
2	Incorrect	4 ms	2924 KB	Output isn't correct
3	Incorrect	5 ms	3036 KB	Output isn't correct
4	Incorrect	90 ms	10652 KB	Output isn't correct
5	Incorrect	5 ms	10652 KB	Output isn't correct
6	Incorrect	6 ms	10652 KB	Output isn't correct
7	Incorrect	4 ms	10652 KB	Output isn't correct
8	Incorrect	4 ms	10652 KB	Output isn't correct
9	Incorrect	5 ms	10652 KB	Output isn't correct
10	Incorrect	5 ms	10652 KB	Output isn't correct
11	Incorrect	5 ms	10652 KB	Output isn't correct
12	Incorrect	6 ms	10652 KB	Output isn't correct
13	Incorrect	67 ms	10864 KB	Output isn't correct
14	Incorrect	97 ms	13156 KB	Output isn't correct
15	Incorrect	102 ms	15228 KB	Output isn't correct
16	Incorrect	80 ms	15564 KB	Output isn't correct
17	Incorrect	136 ms	18144 KB	Output isn't correct
18	Incorrect	95 ms	19888 KB	Output isn't correct
19	Incorrect	121 ms	27716 KB	Output isn't correct
20	Incorrect	4 ms	27716 KB	Output isn't correct
21	Incorrect	4 ms	27716 KB	Output isn't correct
22	Incorrect	89 ms	27716 KB	Output isn't correct
23	Incorrect	60 ms	27716 KB	Output isn't correct
24	Incorrect	83 ms	27716 KB	Output isn't correct
25	Incorrect	76 ms	27716 KB	Output isn't correct

Subtask #2

1.2962962963 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	27716 KB	Output isn't correct
2	Incorrect	6 ms	27716 KB	Output isn't correct
3	Correct	87 ms	35172 KB	Output is correct
4	Runtime error	349 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
5	Runtime error	238 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Runtime error	419 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	4 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
8	Runtime error	5 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
9	Runtime error	4 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
10	Runtime error	131 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	129 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Runtime error	131 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	132 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	4 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
15	Runtime error	5 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
16	Runtime error	4 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
17	Runtime error	4 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
18	Runtime error	159 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	147 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	125 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
21	Runtime error	133 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Runtime error	4 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
23	Runtime error	74 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
24	Runtime error	95 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
25	Runtime error	78 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
26	Runtime error	340 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
27	Runtime error	275 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
28	Runtime error	203 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
29	Runtime error	322 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
30	Runtime error	103 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
31	Runtime error	121 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
32	Runtime error	78 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
33	Runtime error	75 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
34	Runtime error	285 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
35	Runtime error	319 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
36	Runtime error	209 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
37	Runtime error	410 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
38	Runtime error	120 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
39	Runtime error	91 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
40	Runtime error	91 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
41	Runtime error	85 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
42	Runtime error	291 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
43	Runtime error	282 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
44	Runtime error	220 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
45	Runtime error	321 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
46	Runtime error	106 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
47	Runtime error	84 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
48	Runtime error	104 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
49	Runtime error	61 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
50	Runtime error	371 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Runtime error	345 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
52	Runtime error	323 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
53	Runtime error	372 ms	132096 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
54	Runtime error	101 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.