제출 #1069084

#제출 시각아이디문제언어결과실행 시간메모리
1069084APROHACKPotemkin cycle (CEOI15_indcyc)C++17
30 / 100
1093 ms2464 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define ff first #define ss second using namespace std; const int N = 1003, R = 100005; int n, r; vector<int>adj[N]; vector<int>ans; vector<pair<int, int> > backedges[N]; int deep[N]; short vis[N]; const int unvisited = -1; const int visited = 0; const int past = 1; void dfs(int u, int parent, int d){ deep[u] = d; vis[u] = visited; for(auto v : adj[u]){ if(v == parent)continue; if(vis[v] == unvisited){ dfs(v, u, d + 1); }else if(vis[v] == past)continue; else{ backedges[u].pb({deep[v], v}); } } vis[u] = past; } vector<int>stk; bool respond(int u, int parent, int deepest){ vis[u] = visited; stk.pb(u); //sort(backedges[u].rbegin(), backedges[u].rend()); // mahyor a menor. if(!backedges[u].empty()){ int maxDep = -1; int v = -1; for(int i = 0 ; i < backedges[u].size() ; i ++){ if(backedges[u][i].ff > maxDep){ maxDep = backedges[u][i].ff; v = backedges[u][i].ss; } } int d = maxDep; if(d > deepest && abs(d - deep[u]) >= 3){ for(int i = (int)stk.size() - 1 ; stk[i] != v ; i --){ ans.pb(stk[i]); } ans.pb(v); return true; } deepest = max(deepest, d); } for(auto v : adj[u]){ if(parent == v)continue; if(vis[v] == visited)continue; if(respond(v, u, deepest))return true; } stk.pop_back(); vis[u] = past; return false; } int main(){ cin.tie(0); cout.tie(0); ios::sync_with_stdio(NULL); cin >> n >> r; for(int i = 0 ; i < r ; i ++){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } for(int i = 1 ; i <= n ; i ++)vis[i] = unvisited; dfs(1, -1, 0); for(int i = 1 ; i <= n ; i ++)vis[i] = unvisited; if(!respond(1, -1, -10))cout << "no"; else{ for(auto i : ans)cout << i << " "; } }

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

indcyc.cpp: In function 'bool respond(int, int, int)':
indcyc.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i = 0 ; i < backedges[u].size() ; i ++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
#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...