Submission #802916

#	Time	Username	Problem	Language	Result	Execution time	Memory
802916		tch1cherin	Pipes (BOI13_pipes)	C++17	74.07 / 100	1075 ms	131072 KiB

pipes

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  if (M > N) {
    cout << 0 << "\n";
    exit(0);
  }
  vector<int64_t> c(N);
  for (auto &v : c) {
    cin >> v;
  }
  vector<vector<pair<int, int>>> G(N);
  vector<int> d(N);
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    d[u]++, d[v]++;
    G[u].push_back({v, i});
    G[v].push_back({u, i});
  }
  vector<int> x(M);
  queue<int> q;
  for (int i = 0; i < N; i++) {
    if (d[i] == 1) {
      q.push(i);
    }
  }
  vector<bool> used(N);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    used[u] = true;
    for (auto [v, i] : G[u]) {
      if (!used[v]) {
        x[i] = c[u];
        c[v] -= c[u];
        d[v]--;
        if (d[v] == 1) {
          q.push(v);
        }
      }
    }
  }
  if (count(used.begin(), used.end(), false) % 2 == 0 && N == M) {
    cout << "0\n";
    exit(0);
  }
  if (N == M) {
    vector<int> cycle, cycle_edges;
    for (int i = 0; i < N; i++) {
      if (!used[i]) {
        int j = i, last = -1;
        while (j != i || last == -1) {
          cycle.push_back(j);
          for (auto [v, i] : G[j]) {
            if (v != last) {
              cycle_edges.push_back(i);
              last = j;
              j = v;
              break;
            }
          }
        }
        break;
      }
    }
    while (1);
    while (cycle.empty());
    while (cycle.size() != cycle_edges.size());
    int k = (int)cycle.size();
    int64_t sum = 0;
    for (int i = 0; i < k; i++) {
      sum += c[cycle[i]] * (i % 2 ? -1 : 1);
    }
    sum /= 2;
    x[cycle_edges.back()] = sum;
    int64_t last = sum;
    for (int i = 0; i < k - 1; i++) {
      x[cycle_edges[i]] = c[cycle[i]] - last;
      last = x[cycle_edges[i]];
    }
  }
  for (int i = 0; i < M; i++) {
    cout << x[i] * 2 << "\n"; 
  }
}

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