Submission #23496

#TimeUsernameProblemLanguageResultExecution timeMemory
23496ruhanhabib39Potemkin cycle (CEOI15_indcyc)C++14
50 / 100
1000 ms2304 KiB
#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 (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);
                                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...