Submission #116967

#	Time	Username	Problem	Language	Result	Execution time	Memory
116967		IOrtroiii	Potemkin cycle (CEOI15_indcyc)	C++14	100 / 100	405 ms	2936 KiB

indcyc

#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 / 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