oj.uz

Submission #1079070

# Submission time Handle Problem Language Result Execution time Memory
1079070 2024-08-28T10:23:32 Z jk_ Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 166 ms 89288 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, r; cin >> n >> r;

  vector<vector<pair<int, int>>> g(n);
  vector<pair<int, int>> edges;
  vector<vector<bool>> m(n, vector<bool>(n));
  for (int i = 0; i < n; ++i)
    m[i][i] = true;
  for (int i = 0; i < r; ++i) {
    int a, b; cin >> a >> b; --a; --b;
    g[a].emplace_back(b, 2*i);
    g[b].emplace_back(a, 2*i+1);
    edges.emplace_back(a, b);
    edges.emplace_back(b, a);
    m[a][b] = true;
    m[b][a] = true;
  }
  vector<vector<int>> h(2*r);
  for (int e = 0; e < 2*r; ++e) {
    auto [u, v] = edges[e];
    for (auto [w, f] : g[v])
      if (w != u && !m[u][w])
        h[e].push_back(f);
  }

  vector<int> color(2*r);
  vector<int> stack;
  vector<int> answer;
  auto dfs = [&](auto&& self, int v, int p) -> bool {
    if (color[v] == 1) {
      assert(count(stack.begin(), stack.end(), v)>=1);
      answer.push_back(edges[v].first);
      while (stack.back() != v) {
        answer.push_back(edges[stack.back()].first);
        stack.pop_back();
      }
      return true;
    }
    if (color[v] == 2)
      return false;
    color[v] = 1;
    stack.push_back(v);
    for (auto w : h[v])
      if (w != p)
        if (self(self, w, v))
          return true;
    stack.pop_back();
    color[v] = 2;
    return false;
  };
  for (int i = 0; i < 2*r; ++i) {
    assert(stack.empty());
    if (color[i]==0)
      if (dfs(dfs, i, -1))
        break;
  }
  if (answer.empty()) {
    cout << "no\n";
  } else {
    for (int i = 0; i < (int)answer.size(); ++i)
      cout << answer[i]+1 << ' ';
    cout << '\n';
  }
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:23:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     auto [u, v] = edges[e];
      |          ^
indcyc.cpp:24:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |     for (auto [w, f] : g[v])
      |               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 6 ms 3120 KB Output is correct
4 Correct 8 ms 3084 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2140 KB Output is correct
2 Correct 4 ms 2140 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 20168 KB Output is correct
2 Correct 20 ms 5584 KB Output is correct
3 Correct 69 ms 20164 KB Output is correct
4 Correct 19 ms 5588 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 46796 KB Output is correct
2 Correct 78 ms 50884 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 10008 KB Output is correct
2 Correct 102 ms 9916 KB Output is correct
3 Correct 130 ms 89288 KB Output is correct
4 Correct 166 ms 89284 KB Output is correct