Submission #23497

#	Time	Username	Problem	Language	Result	Execution time	Memory
23497		ruhanhabib39	Potemkin cycle (CEOI15_indcyc)	C++14	50 / 100	1000 ms	2316 KiB

indcyc

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

const int MAXN = 300;

int N, M;
set<int> G[MAXN + 10];
bitset<MAXN+1> nxt[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);
      dt.bad |= nxt[back()];
      return dt;
   }
};

void work(int u, dat dt) {
   // if(dt.at(0) == 2) cerr << "u = " << u << "\n";
   if(dt.size() >= 4) {
      if(nxt[u].test(dt.at(0))) {
         for(int x : dt.vec) {
            printf("%d ", x);
         }
         printf("\n");
         exit(0);
      }
   }
   if(dt.size() > 2 && nxt[u].test(dt.at(0))) 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";
      }
   }
}

// void work(int u, int v) {
//    auto e = nxt[u] | nxt[v];
//    if(e.count() >= 2) {
//       printf("%d", u);
//       for(int k = 1; k <= n; k++) {
         
//       }
//       printf(" %d\n", v);
//    }
// }

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); nxt[u].set(v);
      G[v].insert(u); nxt[v].set(u);
   }
   // for(int u = 1; u <= N; u++) {
   //    for(int v = 1; v <= N; v++) {
   //       if(u == v || nxt[u].test(v)) continue;
         
   //    }
   // }
   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:74: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:76: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