Submission #1078997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078997		jk_	Potemkin cycle (CEOI15_indcyc)	C++14	100 / 100	191 ms	6740 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, r; cin >> n >> r;
  if (n <= 3) {
    cout << "no\n";
    return 0;
  }

  vector<vector<int>> g(n);
  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].push_back(b);
    g[b].push_back(a);
    m[a][b] = true;
    m[b][a] = true;
  }
  auto complete_path = [&](int a, int mid, int c) -> vector<int> {
    assert(!m[a][c]);
    vector<int> prev(n, -1);
    queue<int> q; prev[a] = mid; q.push(a);
    while (!q.empty()) {
      int v = q.front(); q.pop();
      for (auto w : g[v]) {
        if (prev[w] != -1) continue;
        prev[w] = v;
        if (w == c) {
          vector<int> path;
          while (w != mid) {
            path.push_back(w);
            w = prev[w];
          }
          path.push_back(mid);
          return path;
        }
        if (m[w][mid]) continue;
        q.push(w);
      }
    }
    assert(false);
    return {};
  };

  auto solve = [&](auto&& self, int root, vector<int> vertices, vector<int> clique) -> vector<int> {
    assert(is_sorted(vertices.begin(), vertices.end()));
    assert(is_sorted(clique.begin(), clique.end()));
    auto is_active = [&](int v) { return binary_search(vertices.begin(), vertices.end(), v); };
    auto is_clique = [&](int v) { return binary_search(clique.begin(), clique.end(), v); };

    // cerr << "solving with root="<<root<<" with clique=[";
    // for(auto x : clique) cerr << " " << x;
    // cerr<< "] on V=";
    // for(auto x : vertices) cerr << " " << x;
    // cerr << '\n';

    vector<int> group(n, -1);
    group[root] = 0;
    for (auto x : g[root]) {
      if (is_active(x)) { assert(!is_clique(x)); group[x] = 0; }
    }
    for (auto x : clique) { assert(!is_active(x)); group[x] = 0; }

    int idx=1;
    vector<int> members;
    vector<int> adjacent;

    auto dfs = [&](auto&& self, int v) -> void {
      if (group[v] != -1 || !is_active(v)) return;
      group[v] = idx;
      members.push_back(v);
      for (auto w : g[v]) {
        if (group[w] == 0)
          adjacent.push_back(w);
        else
          self(self, w);
      }
    };

    for (int i : vertices) {
      // cerr <<"v="<<i<<" group="<<group[i]<<'\n';
      if (group[i] == -1) {
        members.clear();
        adjacent.clear();
        idx++;

        dfs(dfs, i);
        sort(adjacent.begin(), adjacent.end());
        adjacent.erase(unique(adjacent.begin(), adjacent.end()), adjacent.end());
        assert(!binary_search(adjacent.begin(), adjacent.end(), root));

        sort(members.begin(), members.end());

        // cerr << "group ";
        // for(auto x : members) cerr << " " << x;
        // cerr << " adjacent cliques ";
        // for(auto x : adjacent) cerr << " " << x;
        // cerr << '\n';

        for (size_t i = 0; i < adjacent.size(); ++i) {
          for (size_t j = i+1; j < adjacent.size(); ++j) {
            if (!m[adjacent[i]][adjacent[j]]) {
              return complete_path(adjacent[i], root, adjacent[j]);
            }
          }
        }

        int new_root;
        if (!adjacent.empty()) {
          new_root = adjacent.back();
          adjacent.pop_back();
        } else if (!members.empty()) {
          new_root = members.back();
          members.pop_back();
        } else {
          continue;
        }
        auto ans = self(self, new_root, members, adjacent);
        if (!ans.empty())
          return ans;
      }
    }
    vector<int> g0 = g[root];
    sort(g0.begin(), g0.end());
    vector<int> new_vertices;
    set_intersection(g0.begin(), g0.end(), vertices.begin(), vertices.end(),
                     back_inserter(new_vertices));
    if (!new_vertices.empty()) {
      int new_root;
      if (clique.empty()) {
        new_root = new_vertices.back();
        new_vertices.pop_back();
      } else {
        new_root = clique.back();
        clique.pop_back();
      }
      // cerr << "self recurse with root="<<new_root<<" adjacent=";
      // for(auto x : new_vertices) cerr << " " << x;
      // cerr << "\n";
      return self(self, new_root, new_vertices, clique);
    }
    return {};
  };
  vector<int> all_vertices_except_0(n-1);
  iota(all_vertices_except_0.begin(), all_vertices_except_0.end(), 1);
  auto ans = solve(solve, 0, all_vertices_except_0, {});
  if (!ans.empty()) {
    cout << ans[0]+1;
    for (int i = 1; i < (int)ans.size(); ++i) {
      cout << " " << ans[i]+1;
      assert(m[ans[i-1]][ans[i]]);
      for (int j = i+2; j < i+(int)ans.size()-2; ++j) {
        assert(!m[ans[i]][ans[j%ans.size()]]);
      }
    }
    cout << '\n';
  } else {
    cout << "no\n";
  }
}

• 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