oj.uz

Submission #757783

# Submission time Handle Problem Language Result Execution time Memory
757783 2023-06-13T18:25:44 Z taher Senior Postmen (BOI14_postmen) C++17
100 / 100
 484 ms 112264 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n);
  vector<array<int, 2>> edges;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(i);
    adj[v].push_back(i);
    edges.push_back({u, v});
  }
  vector<vector<int>> tours;
  vector<bool> visited(m);
  vector<int> sBefore(n);
  vector<int> v;
  function<void(int)> Euler = [&](int head) {
    while ((int) adj[head].size() > 0) {

      auto u = adj[head].back();
      adj[head].pop_back();

      v.push_back(head);
      sBefore[head] += 1;
      
      if (!visited[u]) {
        visited[u] = true;
        int nxt = head ^ edges[u][0] ^ edges[u][1];
        if (sBefore[nxt]) {
          vector<int> cur;
          int p = -1;
          do {
            cur.push_back(1 + v.back());
            p = v.back();
            sBefore[p] -= 1;
            v.pop_back();
          } while (p != nxt);
          tours.push_back(cur);
        } 
        Euler(nxt);
      }

      if ((int) v.size() > 0 && v.back() == head) {
        v.pop_back();
        sBefore[head] -= 1;
      }
    }
    return ;
  };

  Euler(0);

  for (int i = 0; i < (int) tours.size(); i++) {
    for (int j = 0; j < (int) tours[i].size(); j++) {
      cout << tours[i][j] << " \n"[j == (int) tours[i].size() - 1];
    }
  }
  return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 1040 KB Output is correct
7 Correct 6 ms 2708 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 38 ms 16204 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 48 ms 16576 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 6 ms 2772 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 46 ms 16212 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 47 ms 16544 KB Output is correct
13 Correct 85 ms 22464 KB Output is correct
14 Correct 54 ms 14936 KB Output is correct
15 Correct 60 ms 21016 KB Output is correct
16 Correct 65 ms 22464 KB Output is correct
17 Correct 72 ms 9928 KB Output is correct
18 Correct 64 ms 18164 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 7 ms 2768 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 46 ms 16232 KB Output is correct
10 Correct 2 ms 700 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 41 ms 16544 KB Output is correct
13 Correct 86 ms 22464 KB Output is correct
14 Correct 58 ms 14976 KB Output is correct
15 Correct 59 ms 21044 KB Output is correct
16 Correct 74 ms 22552 KB Output is correct
17 Correct 75 ms 9932 KB Output is correct
18 Correct 56 ms 18116 KB Output is correct
19 Correct 446 ms 112212 KB Output is correct
20 Correct 408 ms 74356 KB Output is correct
21 Correct 425 ms 104400 KB Output is correct
22 Correct 473 ms 112264 KB Output is correct
23 Correct 181 ms 78964 KB Output is correct
24 Correct 449 ms 49116 KB Output is correct
25 Correct 484 ms 90764 KB Output is correct