oj.uz

Submission #23496

# Submission time Handle Problem Language Result Execution time Memory
23496 2017-05-11T08:46:47 Z ruhanhabib39 Potemkin cycle (CEOI15_indcyc) C++14
50 / 100
 1000 ms 2304 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300;

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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -