Submission #23495

#	Time	Username	Problem	Language	Result	Execution time	Memory
23495		ruhanhabib39	Potemkin cycle (CEOI15_indcyc)	C++14	50 / 100	146 ms	2164 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;

int N, M;
set<int> G[MAXN + 10];

struct dat {
   deque<int> vec;
   bitset<MAXN+1> bad;

   void reset() {
      vec.clear();
      bad.reset();
   }

   int size() const {
      return vec.size();
   }
   int at(int i) const {
      return vec[i];
   }
   bool is_bad(int u) const {
      return bad.test(u);
   }
   int back() const {
      return vec.back();
   }
   dat add_back(int u) {
      dat dt = *this;
      dt.vec.push_back(u);
      dt.bad.set(u);
      for(int v : G[back()]) {
         dt.bad.set(v);
      }
      return dt;
   }
};

void work(int u, dat dt) {
   // if(dt.at(0) == 2) cerr << "u = " << u << "\n";
   if(dt.size() >= 4) {
      if(G[u].find(dt.at(0)) != G[u].end()) {
         for(int x : dt.vec) {
            printf("%d ", x);
         }
         printf("\n");
         exit(0);
      }
   }
   if(dt.size() > 2 && G[u].find(dt.at(0)) != G[u].end()) return;
   for(int v : G[u]) {
      // if(dt.at(0) == 2) cerr << v << " is bad\n";
      if(!dt.is_bad(v)) {
         // if(dt.at(0) == 2) cerr << ">>>>>>>>>>>>>>>>>>>>>>>>\n";
         work(v, dt.add_back(v));
         // if(dt.at(0) == 2) cerr << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n";
      }
   }
}

int main() {
   scanf("%d%d", &N, &M);
   for(int i = 0; i < M; i++) {
      int u, v; scanf("%d%d", &u, &v);
      G[u].insert(v);
      G[v].insert(u);
   }
   for(int u = 1; u <= N; u++) {
      for(int v : G[u]) {
         dat dt;
         dt.vec.push_back(u); dt.bad.set(u);
         dt.vec.push_back(v); dt.bad.set(v);
         // cerr << u << "-> " << v << "\n";
         work(v, dt);
      }
   }
   printf("no\n");
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:64:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &N, &M);
                         ^
indcyc.cpp:66:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       int u, v; scanf("%d%d", &u, &v);
                                      ^

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