제출 #244565

#제출 시각아이디문제언어결과실행 시간메모리
244565cheehengPotemkin cycle (CEOI15_indcyc)C++14
30 / 100
30 ms4736 KiB
#include <bits/stdc++.h> using namespace std; vector<int> AdjList[1005]; bool visited[1005]; bool AdjMat[1005][1005]; int dist[1005]; int p[1005]; bool forbidden[1005]; int N, R; vector<int> stack1; bool picked[15]; void dfs(int u, int s, int k){ /*printf("dfs(%d, %d, %d): ", u, s, k); for(int x: stack1){ printf("%d ", x); } printf("\n");*/ if(k > N){return;} if(u == s && k > 0){ if(k < 4){return;} bool boleh = true; for(int i = 0; i < (int)stack1.size()-1; i ++){ for(int j = i+2; j < (int)stack1.size()-1; j ++){ if(min(j-i, (int)stack1.size()-1-(j-i)) < 2){continue;} int x = stack1[i]; int y = stack1[j]; if(AdjMat[x][y]){ //printf("%d and %d connected\n", x, y); boleh = false; break; } } if(!boleh){break;} } if(boleh){ stack1.pop_back(); for(int i: stack1){ printf("%d ", i); } exit(0); } }else{ for(int v = 1; v <= N; v ++){ if(AdjMat[u][v] && u != v && !picked[v]){ picked[v] = true; stack1.push_back(v); dfs(v, s, k+1); stack1.pop_back(); picked[v] = false; } } } } int main(){ scanf("%d%d", &N, &R); memset(AdjMat, 0, sizeof(AdjMat)); for(int i = 0; i < R; i ++){ int a, b; scanf("%d%d", &a, &b); AdjList[a].push_back(b); AdjList[b].push_back(a); AdjMat[a][b] = 1; AdjMat[b][a] = 1; } if(N <= 1000){ for(int i = 1; i <= N; i ++){ stack1.clear(); stack1.push_back(i); memset(picked, false, sizeof(picked)); dfs(i, i, 0); } printf("no"); return 0; } memset(visited, 0, sizeof(visited)); for(int i = 1; i <= N; i ++){ queue<int> q; q.push(i); vector<int> component; component.push_back(i); memset(dist, -1, sizeof(dist)); memset(p, -1, sizeof(p)); dist[i] = 0; int x = -1; int y = -1; int minCycle = N+5; while(!q.empty()){ int u = q.front(); q.pop(); bool found = false; for(int v: AdjList[u]){ if(dist[v] == -1){ component.push_back(v); dist[v] = dist[u]+1; p[v] = u; q.push(v); }else if(v != p[u]){ int temp = dist[u]+dist[v] +1 ; if(temp < minCycle){ minCycle = temp; //printf("p[%d]=%d; p[%d]=%d\n", u, p[u], v, p[v]); //found = true; x = u; y = v; } } } if(found){break;} } if(minCycle <= N && minCycle >= 4){ //printf("x=%d y=%d\n", x, y); vector<int> X; vector<int> Y; while(x != -1){ X.push_back(x); x = p[x]; } reverse(X.begin(), X.end()); memset(forbidden, false, sizeof(forbidden)); for(int x: X){ forbidden[x] = true; } /* memset(dist, -1, sizeof(dist)); memset(p, -1, sizeof(p)); dist[i] = 0; while(!q.empty()){ int u = q.front(); q.pop(); for(int v: AdjList[u]){ if(dist[v] == -1 && !forbidden[v]){ component.push_back(v); dist[v] = dist[u]+1; p[v] = u; q.push(v); } } } */ while(y != i){ X.push_back(y); y = p[y]; } for(int k: X){ printf("%d ", k); } return 0; } } printf("no"); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

indcyc.cpp: In function 'int main()':
indcyc.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &R);
     ~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~
#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...