oj.uz

답안 #802910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
802910 2023-08-02T15:46:15 Z tch1cherin Pipes (BOI13_pipes) C++17
74.0741 / 100
 1000 ms 8600 KB 
#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) {
          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 (cycle.empty());
    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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 37 ms 8568 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 30 ms 6836 KB Output is correct
14 Correct 35 ms 8128 KB Output is correct
15 Correct 38 ms 8532 KB Output is correct
16 Correct 32 ms 7276 KB Output is correct
17 Correct 44 ms 8524 KB Output is correct
18 Correct 38 ms 8576 KB Output is correct
19 Correct 49 ms 7892 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 39 ms 8540 KB Output is correct
23 Correct 31 ms 6820 KB Output is correct
24 Correct 37 ms 8600 KB Output is correct
25 Correct 34 ms 7236 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1068 ms 212 KB Time limit exceeded
2 Execution timed out 1083 ms 340 KB Time limit exceeded
3 Correct 38 ms 7372 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Execution timed out 1087 ms 212 KB Time limit exceeded
8 Execution timed out 1081 ms 212 KB Time limit exceeded
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 252 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Execution timed out 1087 ms 212 KB Time limit exceeded
15 Execution timed out 1080 ms 340 KB Time limit exceeded
16 Execution timed out 1070 ms 340 KB Time limit exceeded
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Execution timed out 1078 ms 340 KB Time limit exceeded
23 Execution timed out 1082 ms 6220 KB Time limit exceeded
24 Execution timed out 1078 ms 7756 KB Time limit exceeded
25 Correct 26 ms 7372 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Execution timed out 1082 ms 7252 KB Time limit exceeded
31 Execution timed out 1066 ms 7428 KB Time limit exceeded
32 Execution timed out 1077 ms 8020 KB Time limit exceeded
33 Correct 28 ms 7716 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Execution timed out 1095 ms 7516 KB Time limit exceeded
39 Execution timed out 1055 ms 8140 KB Time limit exceeded
40 Execution timed out 1084 ms 7768 KB Time limit exceeded
41 Correct 26 ms 7472 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 1 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Execution timed out 1083 ms 7324 KB Time limit exceeded
47 Execution timed out 1086 ms 7756 KB Time limit exceeded
48 Execution timed out 1077 ms 7444 KB Time limit exceeded
49 Correct 28 ms 7628 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Execution timed out 1092 ms 7428 KB Time limit exceeded