답안 #83264 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83264	2018-11-06T12:57:07 Z	teomrn	Pipes (BOI13_pipes)	C++14	0 / 100	1000 ms	22572 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]) {
                if (j == -1)
                    while (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:56:9: warning: unused variable 'ce_tata' [-Wunused-variable]
     int ce_tata;
         ^~~~~~~

Subtask #1
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	2680 KB	Output isn't correct
2	Incorrect	4 ms	2808 KB	Output isn't correct
3	Incorrect	4 ms	3016 KB	Output isn't correct
4	Incorrect	69 ms	8672 KB	Output isn't correct
5	Incorrect	4 ms	8672 KB	Output isn't correct
6	Incorrect	4 ms	8672 KB	Output isn't correct
7	Incorrect	4 ms	8672 KB	Output isn't correct
8	Incorrect	4 ms	8672 KB	Output isn't correct
9	Incorrect	5 ms	8672 KB	Output isn't correct
10	Incorrect	4 ms	8672 KB	Output isn't correct
11	Incorrect	6 ms	8672 KB	Output isn't correct
12	Incorrect	4 ms	8672 KB	Output isn't correct
13	Incorrect	63 ms	8672 KB	Output isn't correct
14	Incorrect	67 ms	8672 KB	Output isn't correct
15	Incorrect	71 ms	8736 KB	Output isn't correct
16	Incorrect	67 ms	8736 KB	Output isn't correct
17	Incorrect	69 ms	8736 KB	Output isn't correct
18	Incorrect	71 ms	8796 KB	Output isn't correct
19	Incorrect	79 ms	15152 KB	Output isn't correct
20	Incorrect	4 ms	15152 KB	Output isn't correct
21	Incorrect	4 ms	15152 KB	Output isn't correct
22	Incorrect	70 ms	15152 KB	Output isn't correct
23	Incorrect	56 ms	15152 KB	Output isn't correct
24	Incorrect	72 ms	15152 KB	Output isn't correct
25	Incorrect	60 ms	15152 KB	Output isn't correct

Subtask #2
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	15152 KB	Output isn't correct
2	Incorrect	5 ms	15152 KB	Output isn't correct
3	Incorrect	94 ms	15412 KB	Output isn't correct
4	Execution timed out	1054 ms	19864 KB	Time limit exceeded
5	Execution timed out	1075 ms	19864 KB	Time limit exceeded
6	Execution timed out	1085 ms	19864 KB	Time limit exceeded
7	Incorrect	4 ms	19864 KB	Output isn't correct
8	Incorrect	4 ms	19864 KB	Output isn't correct
9	Incorrect	5 ms	19864 KB	Output isn't correct
10	Incorrect	4 ms	19864 KB	Output isn't correct
11	Incorrect	4 ms	19864 KB	Output isn't correct
12	Incorrect	4 ms	19864 KB	Output isn't correct
13	Execution timed out	1069 ms	19864 KB	Time limit exceeded
14	Incorrect	4 ms	19864 KB	Output isn't correct
15	Incorrect	4 ms	19864 KB	Output isn't correct
16	Incorrect	4 ms	19864 KB	Output isn't correct
17	Incorrect	4 ms	19864 KB	Output isn't correct
18	Execution timed out	1044 ms	19864 KB	Time limit exceeded
19	Execution timed out	1082 ms	19864 KB	Time limit exceeded
20	Execution timed out	1074 ms	19864 KB	Time limit exceeded
21	Execution timed out	1067 ms	19864 KB	Time limit exceeded
22	Incorrect	5 ms	19864 KB	Output isn't correct
23	Incorrect	67 ms	19864 KB	Output isn't correct
24	Incorrect	88 ms	19864 KB	Output isn't correct
25	Incorrect	80 ms	19864 KB	Output isn't correct
26	Execution timed out	1087 ms	19864 KB	Time limit exceeded
27	Incorrect	105 ms	19864 KB	Output isn't correct
28	Execution timed out	1066 ms	19864 KB	Time limit exceeded
29	Execution timed out	1065 ms	19864 KB	Time limit exceeded
30	Incorrect	127 ms	21292 KB	Output isn't correct
31	Incorrect	98 ms	21836 KB	Output isn't correct
32	Incorrect	75 ms	21836 KB	Output isn't correct
33	Incorrect	81 ms	21836 KB	Output isn't correct
34	Execution timed out	1074 ms	21836 KB	Time limit exceeded
35	Execution timed out	1073 ms	21836 KB	Time limit exceeded
36	Execution timed out	1069 ms	21836 KB	Time limit exceeded
37	Execution timed out	1083 ms	21836 KB	Time limit exceeded
38	Incorrect	91 ms	21836 KB	Output isn't correct
39	Incorrect	69 ms	21836 KB	Output isn't correct
40	Incorrect	73 ms	21836 KB	Output isn't correct
41	Incorrect	82 ms	21836 KB	Output isn't correct
42	Execution timed out	1056 ms	21836 KB	Time limit exceeded
43	Incorrect	99 ms	21836 KB	Output isn't correct
44	Execution timed out	1057 ms	21836 KB	Time limit exceeded
45	Execution timed out	1073 ms	21836 KB	Time limit exceeded
46	Incorrect	91 ms	22572 KB	Output isn't correct
47	Incorrect	80 ms	22572 KB	Output isn't correct
48	Incorrect	79 ms	22572 KB	Output isn't correct
49	Incorrect	66 ms	22572 KB	Output isn't correct
50	Execution timed out	1060 ms	22572 KB	Time limit exceeded
51	Execution timed out	1078 ms	22572 KB	Time limit exceeded
52	Execution timed out	1073 ms	22572 KB	Time limit exceeded
53	Execution timed out	1071 ms	22572 KB	Time limit exceeded
54	Incorrect	73 ms	22572 KB	Output isn't correct

답안 #83264

Compilation message

Subtask #1 0 / 30.0

Subtask #2 0 / 70.0

Subtask #1
0 / 30.0

Subtask #2
0 / 70.0