Submission #1079070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079070		jk_	Potemkin cycle (CEOI15_indcyc)	C++14	100 / 100	166 ms	89288 KiB

indcyc

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10