Submission #34658

#TimeUsernameProblemLanguageResultExecution timeMemory
34658mohammad_kilaniPotemkin cycle (CEOI15_indcyc)C++14
70 / 100
69 ms133112 KiB
#include <bits/stdc++.h> using namespace std; #define mod 1000000007 #define oo 2000000000 const int N =310; bitset< N > con[N] ; int n, m , vi = 0 , vis[N] , pre[N]; vector<int> g[N]; bool BFS(int s,int e){ vi++; queue < pair<int,int> > q; vis[s] = vi; pre[s] = s; for(int i=0;i<g[s].size();i++){ int node = g[s][i]; if(node == e || (con[node][e])) continue; vis[node] = vi; q.push(make_pair(node,s)); } while(!q.empty()){ int node = q.front().first; int last = q.front().second; q.pop(); pre[node] = last; if(node == e) return true; for(int i=0;i<g[node].size();i++){ int newnode = g[node][i]; if(vis[newnode] == vi || (con[newnode][s] && con[newnode][e])) continue; vis[newnode] = vi; q.push(make_pair(newnode,node)); } } return false; } int main() { //freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ int u ,v; scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); con[u][v] = con[v][u] = true; } for(int i=1;i<=n;i++){ for(int j=0;j<g[i].size();j++){ if(i > g[i][j]) continue; if(BFS(i,g[i][j])){ int cur = g[i][j]; while(pre[cur] != cur){ printf("%d ",cur); cur = pre[cur]; } printf("%d\n",cur); return 0; } } } puts("no"); return 0; }

Compilation message (stderr)

indcyc.cpp: In function 'bool BFS(int, int)':
indcyc.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++){
               ^
indcyc.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[node].size();i++){
                ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[i].size();j++){
                ^
indcyc.cpp:39:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
indcyc.cpp:42:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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...