답안 #83258 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83258	2018-11-06T12:28:48 Z	teomrn	Pipes (BOI13_pipes)	C++14	45.5556 / 100	285 ms	127724 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] != 0) {
            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]) {
                assert(j != -1);
                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 });
        }
    }

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

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

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

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

    return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2808 KB	Output is correct
2	Correct	4 ms	2912 KB	Output is correct
3	Correct	4 ms	3024 KB	Output is correct
4	Correct	97 ms	10620 KB	Output is correct
5	Correct	4 ms	10620 KB	Output is correct
6	Correct	4 ms	10620 KB	Output is correct
7	Correct	4 ms	10620 KB	Output is correct
8	Correct	5 ms	10620 KB	Output is correct
9	Correct	5 ms	10620 KB	Output is correct
10	Correct	5 ms	10620 KB	Output is correct
11	Correct	5 ms	10620 KB	Output is correct
12	Correct	5 ms	10620 KB	Output is correct
13	Correct	68 ms	10932 KB	Output is correct
14	Correct	91 ms	13328 KB	Output is correct
15	Correct	76 ms	15192 KB	Output is correct
16	Correct	83 ms	15616 KB	Output is correct
17	Correct	89 ms	18120 KB	Output is correct
18	Correct	94 ms	19784 KB	Output is correct
19	Correct	149 ms	27700 KB	Output is correct
20	Correct	4 ms	27700 KB	Output is correct
21	Correct	5 ms	27700 KB	Output is correct
22	Correct	89 ms	27700 KB	Output is correct
23	Correct	66 ms	27700 KB	Output is correct
24	Correct	81 ms	27700 KB	Output is correct
25	Correct	73 ms	27700 KB	Output is correct

Subtask #2
15.5555555556 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	27700 KB	Output isn't correct
2	Incorrect	5 ms	27700 KB	Output isn't correct
3	Correct	117 ms	35212 KB	Output is correct
4	Runtime error	118 ms	58748 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	68 ms	58748 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	239 ms	64852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Incorrect	5 ms	64852 KB	Output isn't correct
8	Incorrect	4 ms	64852 KB	Output isn't correct
9	Correct	4 ms	64852 KB	Output is correct
10	Correct	4 ms	64852 KB	Output is correct
11	Correct	4 ms	64852 KB	Output is correct
12	Correct	4 ms	64852 KB	Output is correct
13	Runtime error	11 ms	64852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Incorrect	4 ms	64852 KB	Output isn't correct
15	Incorrect	4 ms	64852 KB	Output isn't correct
16	Incorrect	4 ms	64852 KB	Output isn't correct
17	Correct	5 ms	64852 KB	Output is correct
18	Runtime error	8 ms	64852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	9 ms	64852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	9 ms	64852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Runtime error	9 ms	64852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Incorrect	4 ms	64852 KB	Output isn't correct
23	Incorrect	82 ms	64852 KB	Output isn't correct
24	Incorrect	105 ms	64852 KB	Output isn't correct
25	Correct	70 ms	64852 KB	Output is correct
26	Runtime error	92 ms	69892 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Correct	73 ms	72332 KB	Output is correct
28	Runtime error	68 ms	72332 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Runtime error	237 ms	74092 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Incorrect	114 ms	82040 KB	Output isn't correct
31	Incorrect	119 ms	85160 KB	Output isn't correct
32	Incorrect	115 ms	85160 KB	Output isn't correct
33	Correct	82 ms	85160 KB	Output is correct
34	Runtime error	114 ms	85160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	113 ms	90416 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	80 ms	90416 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Runtime error	285 ms	96556 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Incorrect	116 ms	100192 KB	Output isn't correct
39	Incorrect	86 ms	100192 KB	Output isn't correct
40	Incorrect	86 ms	100192 KB	Output isn't correct
41	Correct	96 ms	107712 KB	Output is correct
42	Runtime error	113 ms	107712 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Correct	94 ms	107712 KB	Output is correct
44	Runtime error	64 ms	107712 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	216 ms	108012 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Incorrect	130 ms	116944 KB	Output isn't correct
47	Incorrect	111 ms	116944 KB	Output isn't correct
48	Incorrect	122 ms	120036 KB	Output isn't correct
49	Correct	75 ms	120036 KB	Output is correct
50	Runtime error	203 ms	120036 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
51	Runtime error	141 ms	120036 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
52	Runtime error	77 ms	120036 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	225 ms	124716 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Incorrect	108 ms	127724 KB	Output isn't correct

답안 #83258

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 15.5555555556 / 70.0

Subtask #1
30.0 / 30.0

Subtask #2
15.5555555556 / 70.0