답안 #83262 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83262	2018-11-06T12:52:13 Z	teomrn	Pipes (BOI13_pipes)	C++14	0 / 100	304 ms	40280 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 });
        }
    }

    return 0;

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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	2680 KB	Output isn't correct
2	Incorrect	4 ms	2840 KB	Output isn't correct
3	Incorrect	4 ms	2856 KB	Output isn't correct
4	Incorrect	78 ms	9052 KB	Output isn't correct
5	Incorrect	5 ms	9052 KB	Output isn't correct
6	Incorrect	4 ms	9052 KB	Output isn't correct
7	Incorrect	4 ms	9052 KB	Output isn't correct
8	Incorrect	4 ms	9052 KB	Output isn't correct
9	Incorrect	5 ms	9052 KB	Output isn't correct
10	Incorrect	6 ms	9052 KB	Output isn't correct
11	Incorrect	5 ms	9052 KB	Output isn't correct
12	Incorrect	5 ms	9052 KB	Output isn't correct
13	Incorrect	57 ms	9052 KB	Output isn't correct
14	Incorrect	64 ms	9052 KB	Output isn't correct
15	Incorrect	67 ms	9232 KB	Output isn't correct
16	Incorrect	59 ms	9232 KB	Output isn't correct
17	Incorrect	73 ms	9232 KB	Output isn't correct
18	Incorrect	74 ms	9232 KB	Output isn't correct
19	Incorrect	112 ms	15580 KB	Output isn't correct
20	Incorrect	4 ms	15580 KB	Output isn't correct
21	Incorrect	4 ms	15580 KB	Output isn't correct
22	Incorrect	72 ms	15580 KB	Output isn't correct
23	Incorrect	55 ms	15580 KB	Output isn't correct
24	Incorrect	99 ms	15580 KB	Output isn't correct
25	Incorrect	105 ms	15580 KB	Output isn't correct

Subtask #2
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	15580 KB	Output isn't correct
2	Incorrect	6 ms	15580 KB	Output isn't correct
3	Incorrect	92 ms	15768 KB	Output isn't correct
4	Runtime error	121 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	72 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	271 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Incorrect	4 ms	38808 KB	Output isn't correct
8	Incorrect	4 ms	38808 KB	Output isn't correct
9	Incorrect	4 ms	38808 KB	Output isn't correct
10	Incorrect	4 ms	38808 KB	Output isn't correct
11	Incorrect	4 ms	38808 KB	Output isn't correct
12	Incorrect	4 ms	38808 KB	Output isn't correct
13	Runtime error	12 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Incorrect	4 ms	38808 KB	Output isn't correct
15	Incorrect	5 ms	38808 KB	Output isn't correct
16	Incorrect	6 ms	38808 KB	Output isn't correct
17	Incorrect	5 ms	38808 KB	Output isn't correct
18	Runtime error	8 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	8 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	9 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Runtime error	13 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Incorrect	6 ms	38808 KB	Output isn't correct
23	Incorrect	122 ms	38808 KB	Output isn't correct
24	Incorrect	89 ms	38808 KB	Output isn't correct
25	Incorrect	87 ms	38808 KB	Output isn't correct
26	Runtime error	102 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Incorrect	91 ms	38808 KB	Output isn't correct
28	Runtime error	73 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Runtime error	246 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Incorrect	91 ms	38808 KB	Output isn't correct
31	Incorrect	104 ms	38808 KB	Output isn't correct
32	Incorrect	82 ms	38808 KB	Output isn't correct
33	Incorrect	86 ms	38808 KB	Output isn't correct
34	Runtime error	100 ms	38808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	120 ms	39008 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	76 ms	39008 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Runtime error	304 ms	39008 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Incorrect	107 ms	39008 KB	Output isn't correct
39	Incorrect	87 ms	39008 KB	Output isn't correct
40	Incorrect	85 ms	39008 KB	Output isn't correct
41	Incorrect	132 ms	40280 KB	Output isn't correct
42	Runtime error	141 ms	40280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Incorrect	93 ms	40280 KB	Output isn't correct
44	Runtime error	97 ms	40280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	232 ms	40280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Incorrect	106 ms	40280 KB	Output isn't correct
47	Incorrect	95 ms	40280 KB	Output isn't correct
48	Incorrect	97 ms	40280 KB	Output isn't correct
49	Incorrect	74 ms	40280 KB	Output isn't correct
50	Runtime error	116 ms	40280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
51	Runtime error	95 ms	40280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
52	Runtime error	107 ms	40280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	238 ms	40280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Incorrect	102 ms	40280 KB	Output isn't correct

답안 #83262

Compilation message

Subtask #1 0 / 30.0

Subtask #2 0 / 70.0

Subtask #1
0 / 30.0

Subtask #2
0 / 70.0