oj.uz

Submission #733992

# Submission time Handle Problem Language Result Execution time Memory
733992 2023-05-01T13:02:09 Z MilosMilutinovic Senior Postmen (BOI14_postmen) C++14
100 / 100
 466 ms 77124 KB 
/**
 *    author:  wxhtzdy
 *    created: 01.05.2023 14:41:43
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<int> u(m), v(m);
  vector<vector<int>> g(n);
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i];
    --u[i]; --v[i];
    g[u[i]].push_back(i);
    g[v[i]].push_back(i);
  }
  vector<bool> rem(m);
  vector<bool> was(n);
  vector<int> ptr(n);
  vector<int> stk;
  function<void(int)> Dfs = [&](int x) {
    if (was[x]) {
      while (stk.size()) {
        int ver = stk.back();
        stk.pop_back();
        cout << ver + 1 << " ";
        was[ver] = false;
        if (ver == x) {
          break;          
        }
      }            
      cout << '\n';
    }
    stk.push_back(x);
    was[x] = true;
    for (; ptr[x] < (int) g[x].size(); ptr[x]++) {
      int e = g[x][ptr[x]];
      if (rem[e]) {
        continue;
      }
      int y = (x ^ u[e] ^ v[e]);
      rem[e] = true;
      ptr[x]++;
      Dfs(y);
      return;
    }     
    stk.pop_back();
    was[x] = false;
  };
  for (int i = 0; i < n; i++) {
    Dfs(i);
  }                                                  
  return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 5 ms 1580 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 29 ms 8740 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 32 ms 8908 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 32 ms 8696 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 39 ms 8948 KB Output is correct
13 Correct 57 ms 14364 KB Output is correct
14 Correct 48 ms 6080 KB Output is correct
15 Correct 51 ms 11972 KB Output is correct
16 Correct 58 ms 15440 KB Output is correct
17 Correct 49 ms 7500 KB Output is correct
18 Correct 58 ms 12160 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 252 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 28 ms 8760 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 34 ms 8932 KB Output is correct
13 Correct 55 ms 14384 KB Output is correct
14 Correct 53 ms 6100 KB Output is correct
15 Correct 46 ms 11944 KB Output is correct
16 Correct 53 ms 15484 KB Output is correct
17 Correct 57 ms 7388 KB Output is correct
18 Correct 56 ms 12172 KB Output is correct
19 Correct 424 ms 77124 KB Output is correct
20 Correct 360 ms 36412 KB Output is correct
21 Correct 387 ms 64184 KB Output is correct
22 Correct 430 ms 77048 KB Output is correct
23 Correct 148 ms 45772 KB Output is correct
24 Correct 456 ms 37164 KB Output is correct
25 Correct 466 ms 60388 KB Output is correct