답안 #83263 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83263	2018-11-06T12:56:34 Z	teomrn	Pipes (BOI13_pipes)	C++14	0 / 100	1000 ms	18140 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]) {
                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:55: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	2836 KB	Output isn't correct
3	Incorrect	5 ms	2932 KB	Output isn't correct
4	Incorrect	93 ms	8128 KB	Output isn't correct
5	Incorrect	4 ms	8128 KB	Output isn't correct
6	Incorrect	4 ms	8128 KB	Output isn't correct
7	Incorrect	4 ms	8128 KB	Output isn't correct
8	Incorrect	5 ms	8128 KB	Output isn't correct
9	Incorrect	4 ms	8128 KB	Output isn't correct
10	Incorrect	5 ms	8128 KB	Output isn't correct
11	Incorrect	4 ms	8128 KB	Output isn't correct
12	Incorrect	4 ms	8128 KB	Output isn't correct
13	Incorrect	49 ms	8128 KB	Output isn't correct
14	Incorrect	83 ms	8128 KB	Output isn't correct
15	Incorrect	72 ms	8172 KB	Output isn't correct
16	Incorrect	59 ms	8172 KB	Output isn't correct
17	Incorrect	70 ms	8180 KB	Output isn't correct
18	Incorrect	74 ms	8316 KB	Output isn't correct
19	Incorrect	84 ms	13040 KB	Output isn't correct
20	Incorrect	4 ms	13040 KB	Output isn't correct
21	Incorrect	4 ms	13040 KB	Output isn't correct
22	Incorrect	77 ms	13040 KB	Output isn't correct
23	Incorrect	54 ms	13040 KB	Output isn't correct
24	Incorrect	96 ms	13040 KB	Output isn't correct
25	Incorrect	70 ms	13040 KB	Output isn't correct

Subtask #2
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1069 ms	13040 KB	Time limit exceeded
2	Execution timed out	1083 ms	13040 KB	Time limit exceeded
3	Execution timed out	1075 ms	13040 KB	Time limit exceeded
4	Execution timed out	1073 ms	16124 KB	Time limit exceeded
5	Execution timed out	1079 ms	16124 KB	Time limit exceeded
6	Execution timed out	1076 ms	18016 KB	Time limit exceeded
7	Execution timed out	1063 ms	18016 KB	Time limit exceeded
8	Execution timed out	1074 ms	18016 KB	Time limit exceeded
9	Execution timed out	1080 ms	18016 KB	Time limit exceeded
10	Execution timed out	1069 ms	18016 KB	Time limit exceeded
11	Execution timed out	1073 ms	18016 KB	Time limit exceeded
12	Execution timed out	1076 ms	18016 KB	Time limit exceeded
13	Execution timed out	1066 ms	18016 KB	Time limit exceeded
14	Execution timed out	1081 ms	18016 KB	Time limit exceeded
15	Execution timed out	1064 ms	18016 KB	Time limit exceeded
16	Execution timed out	1080 ms	18016 KB	Time limit exceeded
17	Execution timed out	1078 ms	18016 KB	Time limit exceeded
18	Execution timed out	1079 ms	18016 KB	Time limit exceeded
19	Execution timed out	1093 ms	18016 KB	Time limit exceeded
20	Execution timed out	1079 ms	18016 KB	Time limit exceeded
21	Execution timed out	1084 ms	18016 KB	Time limit exceeded
22	Execution timed out	1084 ms	18016 KB	Time limit exceeded
23	Execution timed out	1078 ms	18016 KB	Time limit exceeded
24	Execution timed out	1082 ms	18016 KB	Time limit exceeded
25	Execution timed out	1049 ms	18016 KB	Time limit exceeded
26	Execution timed out	1069 ms	18016 KB	Time limit exceeded
27	Execution timed out	1065 ms	18016 KB	Time limit exceeded
28	Execution timed out	1072 ms	18016 KB	Time limit exceeded
29	Execution timed out	1072 ms	18016 KB	Time limit exceeded
30	Execution timed out	1078 ms	18016 KB	Time limit exceeded
31	Execution timed out	1074 ms	18016 KB	Time limit exceeded
32	Execution timed out	1061 ms	18016 KB	Time limit exceeded
33	Execution timed out	1081 ms	18016 KB	Time limit exceeded
34	Execution timed out	1084 ms	18016 KB	Time limit exceeded
35	Execution timed out	1075 ms	18016 KB	Time limit exceeded
36	Execution timed out	1069 ms	18016 KB	Time limit exceeded
37	Execution timed out	1076 ms	18016 KB	Time limit exceeded
38	Execution timed out	1063 ms	18016 KB	Time limit exceeded
39	Execution timed out	1050 ms	18016 KB	Time limit exceeded
40	Execution timed out	1064 ms	18016 KB	Time limit exceeded
41	Execution timed out	1068 ms	18016 KB	Time limit exceeded
42	Execution timed out	1074 ms	18016 KB	Time limit exceeded
43	Execution timed out	1061 ms	18016 KB	Time limit exceeded
44	Execution timed out	1078 ms	18016 KB	Time limit exceeded
45	Execution timed out	1077 ms	18016 KB	Time limit exceeded
46	Execution timed out	1045 ms	18140 KB	Time limit exceeded
47	Execution timed out	1075 ms	18140 KB	Time limit exceeded
48	Execution timed out	1072 ms	18140 KB	Time limit exceeded
49	Execution timed out	1052 ms	18140 KB	Time limit exceeded
50	Execution timed out	1067 ms	18140 KB	Time limit exceeded
51	Execution timed out	1059 ms	18140 KB	Time limit exceeded
52	Execution timed out	1072 ms	18140 KB	Time limit exceeded
53	Execution timed out	1066 ms	18140 KB	Time limit exceeded
54	Execution timed out	1057 ms	18140 KB	Time limit exceeded

답안 #83263

Compilation message

Subtask #1 0 / 30.0

Subtask #2 0 / 70.0

Subtask #1
0 / 30.0

Subtask #2
0 / 70.0