답안 #83267 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83267	2018-11-06T13:00:47 Z	teomrn	Pipes (BOI13_pipes)	C++14	0 / 100	1000 ms	22136 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 activ[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)
{
    activ[nod] = 1;
    for (auto i : adia[nod]) {
        if (i.first == tata[nod])
            continue;
        if (tata[i.first] != 0) {
            if (h[i.first] > h[nod])
                continue;
            assert(activ[i.first]);
            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;
        }
    }
    activ[nod] = 0;
    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:60: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	2804 KB	Output isn't correct
3	Incorrect	4 ms	2880 KB	Output isn't correct
4	Incorrect	74 ms	8280 KB	Output isn't correct
5	Incorrect	4 ms	8280 KB	Output isn't correct
6	Incorrect	4 ms	8280 KB	Output isn't correct
7	Incorrect	4 ms	8280 KB	Output isn't correct
8	Incorrect	5 ms	8280 KB	Output isn't correct
9	Incorrect	4 ms	8280 KB	Output isn't correct
10	Incorrect	6 ms	8280 KB	Output isn't correct
11	Incorrect	5 ms	8280 KB	Output isn't correct
12	Incorrect	4 ms	8280 KB	Output isn't correct
13	Incorrect	57 ms	8280 KB	Output isn't correct
14	Incorrect	81 ms	8280 KB	Output isn't correct
15	Incorrect	76 ms	8316 KB	Output isn't correct
16	Incorrect	66 ms	8316 KB	Output isn't correct
17	Incorrect	74 ms	8316 KB	Output isn't correct
18	Incorrect	82 ms	8316 KB	Output isn't correct
19	Incorrect	84 ms	14716 KB	Output isn't correct
20	Incorrect	5 ms	14716 KB	Output isn't correct
21	Incorrect	4 ms	14716 KB	Output isn't correct
22	Incorrect	93 ms	14716 KB	Output isn't correct
23	Incorrect	50 ms	14716 KB	Output isn't correct
24	Incorrect	69 ms	14716 KB	Output isn't correct
25	Incorrect	64 ms	14716 KB	Output isn't correct

Subtask #2
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	14716 KB	Output isn't correct
2	Incorrect	5 ms	14716 KB	Output isn't correct
3	Incorrect	81 ms	14924 KB	Output isn't correct
4	Execution timed out	1052 ms	19308 KB	Time limit exceeded
5	Execution timed out	1060 ms	19308 KB	Time limit exceeded
6	Execution timed out	1070 ms	19308 KB	Time limit exceeded
7	Incorrect	4 ms	19308 KB	Output isn't correct
8	Incorrect	4 ms	19308 KB	Output isn't correct
9	Incorrect	4 ms	19308 KB	Output isn't correct
10	Incorrect	5 ms	19308 KB	Output isn't correct
11	Incorrect	4 ms	19308 KB	Output isn't correct
12	Incorrect	4 ms	19308 KB	Output isn't correct
13	Execution timed out	1068 ms	19308 KB	Time limit exceeded
14	Incorrect	4 ms	19308 KB	Output isn't correct
15	Incorrect	4 ms	19308 KB	Output isn't correct
16	Incorrect	4 ms	19308 KB	Output isn't correct
17	Incorrect	4 ms	19308 KB	Output isn't correct
18	Execution timed out	1059 ms	19308 KB	Time limit exceeded
19	Execution timed out	1072 ms	19308 KB	Time limit exceeded
20	Execution timed out	1044 ms	19308 KB	Time limit exceeded
21	Execution timed out	1069 ms	19308 KB	Time limit exceeded
22	Incorrect	5 ms	19308 KB	Output isn't correct
23	Incorrect	73 ms	19308 KB	Output isn't correct
24	Incorrect	88 ms	19308 KB	Output isn't correct
25	Incorrect	81 ms	19308 KB	Output isn't correct
26	Execution timed out	1068 ms	19308 KB	Time limit exceeded
27	Incorrect	90 ms	19308 KB	Output isn't correct
28	Execution timed out	1060 ms	19308 KB	Time limit exceeded
29	Execution timed out	1065 ms	19308 KB	Time limit exceeded
30	Incorrect	106 ms	20856 KB	Output isn't correct
31	Incorrect	117 ms	21336 KB	Output isn't correct
32	Incorrect	81 ms	21336 KB	Output isn't correct
33	Incorrect	90 ms	21336 KB	Output isn't correct
34	Execution timed out	1075 ms	21336 KB	Time limit exceeded
35	Execution timed out	1073 ms	21336 KB	Time limit exceeded
36	Execution timed out	1069 ms	21336 KB	Time limit exceeded
37	Execution timed out	1078 ms	21336 KB	Time limit exceeded
38	Incorrect	123 ms	21336 KB	Output isn't correct
39	Incorrect	74 ms	21336 KB	Output isn't correct
40	Incorrect	89 ms	21336 KB	Output isn't correct
41	Incorrect	110 ms	21368 KB	Output isn't correct
42	Execution timed out	1084 ms	21368 KB	Time limit exceeded
43	Incorrect	89 ms	21368 KB	Output isn't correct
44	Execution timed out	1084 ms	21368 KB	Time limit exceeded
45	Execution timed out	1075 ms	21368 KB	Time limit exceeded
46	Incorrect	108 ms	22136 KB	Output isn't correct
47	Incorrect	92 ms	22136 KB	Output isn't correct
48	Incorrect	108 ms	22136 KB	Output isn't correct
49	Incorrect	61 ms	22136 KB	Output isn't correct
50	Execution timed out	1078 ms	22136 KB	Time limit exceeded
51	Execution timed out	1087 ms	22136 KB	Time limit exceeded
52	Execution timed out	1080 ms	22136 KB	Time limit exceeded
53	Execution timed out	1064 ms	22136 KB	Time limit exceeded
54	Incorrect	85 ms	22136 KB	Output isn't correct

답안 #83267

Compilation message

Subtask #1 0 / 30.0

Subtask #2 0 / 70.0

Subtask #1
0 / 30.0

Subtask #2
0 / 70.0