Submission #54884

#TimeUsernameProblemLanguageResultExecution timeMemory
54884ics0503Potemkin cycle (CEOI15_indcyc)C++17
Compilation error
0 ms0 KiB
#include<stdio.h> #include<algorithm> #include<vector> #include<set> using namespace std; vector<int>edge[1212], E[1212]; int depth[1212], is_gone_dfs1[1212]; set<pair<int, int>>L[1212]; set<int>M[1212]; bool sort_e(int a, int b) { return depth[a] < depth[b]; } void dfs1(int w,int dep,int bef) { depth[w] = dep; is_gone_dfs1[w] = 1; for (int i = 0; i < edge[w].size(); i++) { int next = edge[w][i]; if (is_gone_dfs1[next]) { if(next==bef || depth[next] > depth[w])continue; L[w].insert({ depth[next],next }); continue; } E[w].push_back(next); dfs1(next, dep + 1, w); } } int stdep, D[1212], st, go[1212], R[1212], cck, not[1212]; int dfs2(int w, int bef) { set<pair<int, int>>::iterator it = L[w].lower_bound({ stdep + 1,-1e9 }); if (bef != -1 && it == L[w].end())D[w] = D[bef] + 1, go[w] = bef, R[w] = R[bef]; if (bef != -1 && it != L[w].end())D[w] = D[it->second] + 1, go[w] = it->second, R[w] = R[it->second]; if (M[w].find(st) != M[w].end()) { if (D[w] >= 4)return w; if (D[w] == 3) { int x = go[w]; for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 1; for (int i = 0; i < edge[w].size(); i++) { if (D[edge[w][i]] >= 3 && R[x] != R[edge[w][i]] && !not[R[edge[w][i]]]) { go[w] = edge[w][i]; return w; } } for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 0; } D[w] = 2, go[w] = st; R[w] = w; } for (int i = 0; i < E[w].size(); i++){ int next = E[w][i]; int k = dfs2(next, w); if (k) return k; } return 0; } int main() { int n, m; scanf("%d%d", &n, &m); int i, j; for (i = 0; i < m; i++) { int s, e; scanf("%d%d", &s, &e); edge[s].push_back(e); M[s].insert(e); edge[e].push_back(s); M[e].insert(s); } for (i = 1; i <= n; i++) { if (is_gone_dfs1[i])continue; dfs1(i, 1, -1); } for (i = 1; i <= n; i++)sort(edge[i].begin(), edge[i].end(),sort_e); for (i = 1; i <= n; i++) { D[i] = 1; R[i] = st = i; stdep = depth[i]; int now = dfs2(i, -1); if (now) { while (now != i) { printf("%d ", now); now = go[now]; } printf("%d ", i); return 0; } for (j = 1; j <= n; j++)D[j] = R[j] = go[j] = 0; } printf("no"); return 0; }

Compilation message (stderr)

indcyc.cpp: In function 'void dfs1(int, int, int)':
indcyc.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edge[w].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~
indcyc.cpp: At global scope:
indcyc.cpp:23:49: error: expected unqualified-id before 'not' token
 int stdep, D[1212], st, go[1212], R[1212], cck, not[1212];
                                                 ^~~
indcyc.cpp: In function 'int dfs2(int, int)':
indcyc.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 1;
                    ~~^~~~~~~~~~~~~~~~
indcyc.cpp:32:72: warning: capture of variable 'edge' with non-automatic storage duration
    for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 1;
                                                                        ^~~~
indcyc.cpp:6:12: note: 'std::vector<int> edge [1212]' declared here
 vector<int>edge[1212], E[1212];
            ^~~~
indcyc.cpp:32:76: error: expected ',' before '[' token
    for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 1;
                                                                            ^
indcyc.cpp:32:76: error: expected identifier before '[' token
indcyc.cpp: In lambda function:
indcyc.cpp:32:84: error: expected '{' before '=' token
    for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 1;
                                                                                    ^
indcyc.cpp: In function 'int dfs2(int, int)':
indcyc.cpp:32:84: warning: the address of 'static constexpr void dfs2(int, int)::<lambda()>::_FUN()' will never be NULL [-Waddress]
indcyc.cpp:32:84: warning: the address of 'static constexpr void dfs2(int, int)::<lambda()>::_FUN()' will never be NULL [-Waddress]
indcyc.cpp:32:86: error: lvalue required as left operand of assignment
    for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 1;
                                                                                      ^
indcyc.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < edge[w].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~
indcyc.cpp:34:61: warning: capture of variable 'R' with non-automatic storage duration
     if (D[edge[w][i]] >= 3 && R[x] != R[edge[w][i]] && !not[R[edge[w][i]]]) {
                                                             ^
indcyc.cpp:23:35: note: 'int R [1212]' declared here
 int stdep, D[1212], st, go[1212], R[1212], cck, not[1212];
                                   ^
indcyc.cpp:34:62: error: expected ',' before '[' token
     if (D[edge[w][i]] >= 3 && R[x] != R[edge[w][i]] && !not[R[edge[w][i]]]) {
                                                              ^
indcyc.cpp:34:62: error: expected identifier before '[' token
indcyc.cpp: In lambda function:
indcyc.cpp:34:75: error: expected '{' before ')' token
     if (D[edge[w][i]] >= 3 && R[x] != R[edge[w][i]] && !not[R[edge[w][i]]]) {
                                                                           ^
indcyc.cpp: In function 'int dfs2(int, int)':
indcyc.cpp:34:75: warning: the address of 'static constexpr void dfs2(int, int)::<lambda()>::_FUN()' will never be NULL [-Waddress]
indcyc.cpp:34:75: warning: the address of 'static constexpr void dfs2(int, int)::<lambda()>::_FUN()' will never be NULL [-Waddress]
indcyc.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 0;
                    ~~^~~~~~~~~~~~~~~~
indcyc.cpp:39:72: warning: capture of variable 'edge' with non-automatic storage duration
    for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 0;
                                                                        ^~~~
indcyc.cpp:6:12: note: 'std::vector<int> edge [1212]' declared here
 vector<int>edge[1212], E[1212];
            ^~~~
indcyc.cpp:39:76: error: expected ',' before '[' token
    for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 0;
                                                                            ^
indcyc.cpp:39:76: error: expected identifier before '[' token
indcyc.cpp: In lambda function:
indcyc.cpp:39:84: error: expected '{' before '=' token
    for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 0;
                                                                                    ^
indcyc.cpp: In function 'int dfs2(int, int)':
indcyc.cpp:39:84: warning: the address of 'static constexpr void dfs2(int, int)::<lambda()>::_FUN()' will never be NULL [-Waddress]
indcyc.cpp:39:84: warning: the address of 'static constexpr void dfs2(int, int)::<lambda()>::_FUN()' will never be NULL [-Waddress]
indcyc.cpp:39:86: error: lvalue required as left operand of assignment
    for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)not[edge[w][i]] = 0;
                                                                                      ^
indcyc.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E[w].size(); i++){
                  ~~^~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:51:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d%d", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d%d", &s, &e);
             ~~~~~^~~~~~~~~~~~~~~~