Submission #974993

#	Time	Username	Problem	Language	Result	Execution time	Memory
974993		duckindog	Potemkin cycle (CEOI15_indcyc)	C++17	20 / 100	12 ms	5296 KiB

indcyc

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n, m;
vector<int> ad[N];

int par[N], d[N];
bool vst[N], mk[N];

void dfs1(int u, int p = 0) { 
  par[u] = p;
  d[u] = d[p] + 1;
  vst[u] = true;

  for (const auto& v : ad[u]) { 
    if (v == p || vst[v]) continue;
    dfs1(v, u);
  }
}

vector<int> answer;
vector<int> dep;
void dfs2(int u, int p = 0) { 
  if (answer.size()) return;
  
  sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) { return d[a] < d[b]; });
  
  vst[u] = true;  

  bool pass = false, pushed = false;
  for (const auto& v : ad[u]) { 
    if (v == p && !pass) {
      pass = true;
      continue;
    }

    if (!vst[v]) dfs2(v, u);
    else {

      if (d[u] - d[v] >= 3) { 
        if (!dep.size() || dep.end()[-1] < d[v]) { 
        
          answer.push_back(v);
          while (u != v) {
            answer.push_back(u);
            u = par[u];
          }

          return;
        }
      }
 
      if (pushed) dep.pop_back();
      dep.push_back(!dep.size() ? d[v] : min(dep.end()[-1], d[v]));
      pushed = true;
    }
  }

  if (pushed) dep.pop_back();
}


int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for (int i = 1; i <= m; ++i) { 
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }

  dfs1(1);
  
  memset(vst, false, sizeof vst);

  dfs2(1);
  
  if (!answer.size()) { cout << "no" << "\n"; return 0; }

  for (const auto& x : answer) cout << x << " \n"[x == answer.end()[-1]];
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10