제출 #228496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228496		Fischer	Pipes (BOI13_pipes)	C++14	44.07 / 100	288 ms	15544 KiB

pipes

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Miguel Mini
 */

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define trav(v, x) for (auto v : x)
#define re(x, y, z) for (int x=y; x<z; ++x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set_to(x, v) fill(all(x), v)
#define eb emplace_back
#define lso(x) ((x)&-(x))
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = INT_MAX;
vector<ii> g[maxn];

class pipes {
public:

    void solveOne(istream& in, ostream& out) {
        int n, m;
        in >> n >> m;
        if (m > n) {
            out << 0 << endl;
            return;
        }
        vector<ll> c(n);
        vi deg(n);
        trav(&v, c) in >> v;
        vector<ii> edges;
        re(i, 0, m) {
            int a, b;
            in >> a >> b;
            a -= 1; b -= 1;
            edges.eb(a, b);
            g[a].eb(b, i); deg[a] += 1;
            g[b].eb(a, i); deg[b] += 1;
        }
        vi res(m);
        vector<bool> vis(m);
        queue<int> Q;
        re(i, 0, n) {
            if (sz(g[i]) == 1) {
                Q.push(i);
            }
        }
        while (!Q.empty()) {
            int q = Q.front(); Q.pop();
            for (auto v : g[q]) {
                int id = v.second;
                if (vis[id]) continue;
                vis[id] = 1;
                m -= 1;
                res[id] = 2 * c[q];
                int u = v.first;
                c[u] += c[q];
                deg[u] -= 1;
                if (deg[u] == 1) {
                    Q.push(u);
                }
            }
        }
        if (m == 0) {
            trav(v, res) out << v << endl;
        } else if (m&1) {
            int x = 0;
            while (deg[x] == 0) x += 1;
            if (x == n) {
                out << 0 << endl;
                return;
            }
            ll sum = 0;
            vector<int> t;
            function<int(int, vi&, ll&)> dfs = [&](int v, vi& t, ll& sum)->int {
                if (deg[v] != 2) return -inf;
                sum = c[v] - sum;
                trav(node, g[v]) {
                    if (!vis[node.second]) {
                        vis[node.second] = 1;
                        t.emplace_back(node.second);
                        if (node.first == x) return 1;
                        return dfs(node.first, t, sum) + 1;
                    }
                }
                return -inf;
            };
            if (dfs(x, t, sum) == m) {
                //trav(v, t) cout << v << " "; cout << endl;
                res[t[0]] = sum;
                re(i, 1, sz(t)) {
                    x ^= edges[t[i-1]].first ^ edges[t[i-1]].second;
                    res[t[i]] = 2 * c[x] - sum;
                    sum = res[t[i]];
                }
                trav(v, res) out << v << endl;
            } else out << 0 << endl;
        } else {
            out << 0 << endl;
        }
    }

    void solve(istream& in, ostream& out) {
        int testNumber = 1;
        //in >> testNumber;
        re(tc, 1, testNumber+1) {
            //out << "Case #" << tc << ": ";
            solveOne(in, out);
        }
    }
};


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	pipes solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

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