oj.uz

Submission #974993

# Submission time Handle Problem Language Result Execution time Memory
974993 2024-05-04T09:17:35 Z duckindog Potemkin cycle (CEOI15_indcyc) C++17
20 / 100
 12 ms 5296 KB 
#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.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3672 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3676 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3672 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3676 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3676 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4444 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3932 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 5296 KB Wrong adjacency
2 Halted 0 ms 0 KB -