Submission #83274

#	Time	Username	Problem	Language	Result	Execution time	Memory
83274		teomrn	Pipes (BOI13_pipes)	C++14	74.07 / 100	275 ms	23656 KiB

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) {
                    cout << 0;
                    exit(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]) {
                        cout << 0;
                        exit(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) {
                    cout << 0;
                    exit(0);
                    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()
    {
        //cout << 0;
        //return 0;
        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 (stderr)

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

• Subtask 1: 30 / 30
• Subtask 2: 44.074074074074076 / 70