oj.uz

Submission #116967

# Submission time Handle Problem Language Result Execution time Memory
116967 2019-06-14T09:48:38 Z IOrtroiii Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 405 ms 2936 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n, m;
vector<int> g[N];
bool G[N][N];
int par[N];
bool visit[N];
vector<int> comp;

void findCycle(int u, int v, int lim) {
   queue<int> q;
   par[u] = u;
   q.push(u);
   while (!q.empty()) {
      int x = q.front();
      q.pop();
      if (x == lim || (G[x][lim] && x != u && x != v)) {
         continue;
      }
      for (int y : g[x]) if (y <= lim) {
         if (!par[y]) {
            par[y] = x;
            q.push(y);
         }
      }
   }
   vector<int> ans;
   while (v != u) {
      ans.push_back(v);
      v = par[v];
   }
   ans.push_back(u);
   ans.push_back(lim);
   for (int x : ans) {
      cout << x << " ";
   }
   cout << "\n";
   exit(0);
}

void dfs(int u, int lim) {
   if (visit[u]) return;
   visit[u] = true;
   for (int v : g[u]) if (v <= lim) {
      if (G[v][lim]) {
         comp.push_back(v);
      } else {
         dfs(v, lim);
      }
   }
}

void solve(int lim) {
   for (int i = 1; i <= lim; ++i) {
      visit[i] = false;
   }
   for (int i = 1; i < lim; ++i) if (!G[i][lim] && !visit[i]) {
      comp.clear();
      dfs(i, lim);
      sort(comp.begin(), comp.end());
      comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
      int sz = comp.size();
      for (int j = 0; j < sz; ++j) {
         for (int k = j + 1; k < sz; ++k) {
            if (!G[comp[j]][comp[k]]) {
               findCycle(comp[j], comp[k], lim);
            }
         }
      }
   }
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> n >> m;
   for (int i = 0; i < m; ++i) {
      int u, v;
      cin >> u >> v;
      G[u][v] = G[v][u] = true;
      g[u].push_back(v), g[v].push_back(u);
   }
   for (int i = 1; i <= n; ++i) {
      solve(i);
   }
   cout << "no";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 896 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 12 ms 848 KB Output is correct
4 Correct 13 ms 768 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 768 KB Output is correct
2 Correct 10 ms 768 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 2304 KB Output is correct
2 Correct 39 ms 1792 KB Output is correct
3 Correct 257 ms 2428 KB Output is correct
4 Correct 120 ms 1912 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 1956 KB Output is correct
2 Correct 185 ms 1884 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2560 KB Output is correct
2 Correct 19 ms 2552 KB Output is correct
3 Correct 368 ms 2720 KB Output is correct
4 Correct 405 ms 2936 KB Output is correct