제출 #995736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995736		MilosMilutinovic	Pipes (BOI13_pipes)	C++14	74.07 / 100	93 ms	36556 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<vector<array<int, 2>>> g(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g[x].push_back({y, i});
    g[y].push_back({x, i});
  }
  if (m > n) {
    cout << 0 << '\n';
    return 0;
  }
  if (n == 1) {
    cout << 2 * a[0] << '\n';
    return 0;
  }
  if (m < n) {
    vector<long long> res(m);
    function<void(int, int)> Dfs = [&](int v, int pv) {
      for (auto& e : g[v]) {
        int u = e[0];
        if (u == pv) {
          continue;
        }
        Dfs(u, v);
        if (a[u] != 0) {
          res[e[1]] = 2 * a[u];
          a[v] -= a[u];
        }
      }
    };
    Dfs(0, 0);
    if (a[0] != 0) {
      cout << 0 << '\n';
      return 0;
    }
    for (int i = 0; i < m; i++) {
      cout << res[i] << '\n';
    }
    return 0;
  }
  vector<int> deg(n);
  for (int i = 0; i < n; i++) {
    deg[i] = (int) g[i].size();
  }
  vector<int> que;
  for (int i = 0; i < n; i++) {
    if (deg[i] == 1) {
      que.push_back(i);
    }
  }
  auto orig = a;
  vector<long long> res(m);
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    for (auto& e : g[i]) {
      int j = e[0];
      deg[j] -= 1;
      if (deg[j] == 1) {
        que.push_back(j);
        res[e[1]] = 2 * a[i];
        a[j] -= a[i];
      }
    }
  }
  vector<int> cyc;
  for (int i = 0; i < n; i++) {
    if (deg[i] > 1) {
      cyc.push_back(i);
    }
  }
  if ((int) cyc.size() % 2 == 0) {
    cout << 0 << '\n';
    return 0;
  }
  vector<bool> was(n);
  vector<long long> vals;
  vector<int> ids;
  function<void(int)> Dfs = [&](int v) {
    was[v] = true;
    vals.push_back(a[v]);
    int back = -1;
    bool found = false;
    for (auto& e : g[v]) {
      int u = e[0];
      int i = e[1];
      if (u == cyc[0]) {
        back = i;
      }
      if (was[u]) {
        continue;
      }
      found = true;
      ids.push_back(i);
      Dfs(u);
    }
    if (!found) {
      ids.push_back(back);
    }
  }; 
  Dfs(cyc[0]);
  long long total = 0;
  for (int i = 0; i < (int) vals.size(); i++) {
    total = vals[i] - total;
  }
  res[ids.back()] = 2 * total;
  for (int i = 0; i < n; i++) {
    for (auto& p : g[i]) {
      if (p[2] == ids.back()) {
        a[i] -= total;
      }
    }
  }
  was = vector<bool>(n, false);
  Dfs = [&](int v) {
    was[v] = true;
    for (auto& p : g[v]) {
      int u = p[0];
      int i = p[1];
      if (deg[u] <= 1 || was[u]) {
        continue;
      }
      Dfs(u);
      res[i] = 2 * a[u];
      a[v] -= a[u];
    }
  };
  Dfs(cyc.back());
  if (a != vector<long long>(n, 0LL)) {
    cout << 0 << '\n';
    return 0;
  }
  for (int i = 0; i < m; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}

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