oj.uz

Submission #975079

# Submission time Handle Problem Language Result Execution time Memory
975079 2024-05-04T11:43:55 Z duckindog Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 39 ms 10580 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 10;
int n, m;
vector<int> ad[N];
bool mk[N][N];
int used[N][N], trace[N][N];

void dfs(int u, int v, int p = 0) { 
  used[u][v] = 1;
  trace[u][v] = p;
  for (const auto& x : ad[v]) { 
    if (mk[u][x]) continue;
    if (used[v][x] == 1) {
      while (v != x) { 
        cout << v << " ";
        tie(u, v) = make_pair(trace[u][v], u);
      }
      cout << x << "\n";
      exit(0);
    } else if (!used[v][x]) dfs(v, x, u);
  }
  used[u][v] = 2;
}

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);
    mk[u][v] = mk[v][u] = true;
  }
  for (int i = 1; i <= n; ++i) mk[i][i] = true;

  for (int u = 1; u <= n; ++u) {
    for (int v = u + 1; v <= n; ++v) if (mk[u][v] && !used[u][v]) dfs(u, v);
  }

  cout << "no" << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 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 2396 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 5976 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9816 KB Output is correct
2 Correct 8 ms 9820 KB Output is correct
3 Correct 25 ms 10076 KB Output is correct
4 Correct 13 ms 10072 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8540 KB Output is correct
2 Correct 16 ms 9564 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7700 KB Output is correct
2 Correct 39 ms 8016 KB Output is correct
3 Correct 12 ms 8408 KB Output is correct
4 Correct 38 ms 10580 KB Output is correct