oj.uz

Submission #23497

# Submission time Handle Problem Language Result Execution time Memory
23497 2017-05-11T08:57:55 Z ruhanhabib39 Potemkin cycle (CEOI15_indcyc) C++14
50 / 100
 1000 ms 2316 KB 
#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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2316 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 2316 KB Output is correct
2 Execution timed out 1000 ms 2316 KB Execution timed out

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2192 KB Execution killed because of forbidden syscall gettid (186)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2192 KB Execution killed because of forbidden syscall gettid (186)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2192 KB Execution killed because of forbidden syscall gettid (186)
2 Halted 0 ms 0 KB -