Submit Info #48236

Problem Lang User Status Time Memory
Cycle Detection cpp BigBag AC 41 ms 17.43 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
example_01 AC 1 ms 0.68 MiB
example_02 AC 0 ms 0.70 MiB
random_00 AC 30 ms 15.95 MiB
random_01 AC 39 ms 17.43 MiB
random_02 AC 18 ms 9.03 MiB
random_03 AC 10 ms 7.79 MiB
random_04 AC 14 ms 6.89 MiB
random_05 AC 27 ms 14.10 MiB
random_06 AC 28 ms 12.30 MiB
random_07 AC 4 ms 2.38 MiB
random_08 AC 22 ms 11.69 MiB
random_09 AC 10 ms 6.36 MiB
random_dag_00 AC 39 ms 16.03 MiB
random_dag_01 AC 41 ms 17.41 MiB
random_dag_02 AC 22 ms 9.04 MiB
random_dag_03 AC 10 ms 7.79 MiB
random_dag_04 AC 8 ms 6.89 MiB
random_dag_05 AC 36 ms 14.41 MiB
random_dag_06 AC 25 ms 12.21 MiB
random_dag_07 AC 4 ms 2.38 MiB
random_dag_08 AC 30 ms 11.68 MiB
random_dag_09 AC 14 ms 6.41 MiB
random_dag_dense_00 AC 17 ms 8.79 MiB
random_dag_dense_01 AC 18 ms 8.78 MiB
random_dag_dense_02 AC 17 ms 9.66 MiB
random_dag_dense_03 AC 20 ms 8.95 MiB
random_dag_dense_04 AC 19 ms 10.35 MiB
random_dense_00 AC 17 ms 8.76 MiB
random_dense_01 AC 17 ms 8.82 MiB
random_dense_02 AC 16 ms 9.66 MiB
random_dense_03 AC 19 ms 8.89 MiB
random_dense_04 AC 17 ms 10.32 MiB

#include <bits/stdc++.h> using namespace std; const int max_n = 505555, inf = 1000111222; namespace fastio { const int buf_size = 1 << 14; char buf_read[buf_size]; char buf_write[buf_size + 30]; char *ptr_read = buf_read + buf_size; char *ptr_write = buf_write; long long read_int() { auto getChar = []() { if (ptr_read == buf_read + buf_size){ fread(buf_read, 1, buf_size, stdin); ptr_read = buf_read; } return *ptr_read++; }; char c = getChar(); while (c && (c < '0' || c > '9') && c != '-') { c = getChar(); } long long z = 1; if (c == '-') { z = -1; c = getChar(); } long long res = 0; while (c >= '0' && c <= '9'){ res = res * 10 + (c - '0'); c = getChar(); } return z * res; } void write_flush() { fwrite(buf_write, 1, ptr_write - buf_write, stdout); ptr_write = buf_write; } void write_int(long long x) { if (x < 0) { *ptr_write++ = '-'; x = -x; } char *start = ptr_write; if (!x) { *ptr_write++ = '0'; } while (x) { *ptr_write++ = x % 10 + '0'; x /= 10; } reverse(start, ptr_write); if (ptr_write >= buf_write + buf_size) { write_flush(); } } void write_char(char c) { *ptr_write++ = c; if (ptr_write >= buf_write + buf_size) { write_flush(); } } } template<typename Edge> class GraphIterator { public: class OutgoingEdges { public: OutgoingEdges(const GraphIterator *g, int l, int r): g(g), l(l), r(r) { } const Edge* begin() const { if (l == r) { return 0; } return &g->prepared_edges[l]; } const Edge* end() const { if (l == r) { return 0; } return &g->prepared_edges[r]; } private: int l, r; const GraphIterator *g; }; void clear() { prepared_edges.clear(); edges.clear(); start.clear(); prepared = false; } void add_edge(int from, const Edge &e) { assert(!prepared && from >= 0); edges.push_back({from, e}); } void prepare() { assert(!prepared); int n = 0; for (const auto &e : edges) { n = max(n, e.first); } n += 2; start.resize(n); for (const auto &e : edges) { ++start[e.first + 1]; } for (int i = 1; i < n; ++i) { start[i] += start[i - 1]; } prepared_edges.resize(edges.size() + 1); auto counter = start; for (const auto &e : edges) { prepared_edges[counter[e.first]++] = e.second; } prepared = true; } OutgoingEdges operator [] (int from) const { assert(prepared); if (from < 0 || from + 1 >= start.size()) { return {this, 0, 0}; } return {this, start[from], start[from + 1]}; } private: vector<Edge> prepared_edges; vector<pair<int, Edge>> edges; vector<int> start; bool prepared = false; }; int n, m; int used[max_n]; pair<int, int> parent[max_n]; GraphIterator<pair<int, int>> g; void dfs(int v) { used[v] = 1; for (auto [to, id] : g[v]) { if (!used[to]) { parent[to] = {v, id}; dfs(to); } else if (used[to] == 1) { vector<int> ans{id}; int cur = v; while (cur != to) { ans.push_back(parent[cur].second); cur = parent[cur].first; } reverse(ans.begin(), ans.end()); fastio::write_int(ans.size()); fastio::write_char('\n'); for (int x : ans) { fastio::write_int(x); fastio::write_char('\n'); } fastio::write_flush(); exit(0); } } used[v] = 2; } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); n = fastio::read_int(); m = fastio::read_int(); for (int i = 0; i < m; ++i) { int u, v; u = fastio::read_int(); v = fastio::read_int(); g.add_edge(u, {v, i}); } g.prepare(); for (int i = 0; i < n; ++i) { if (!used[i]) { dfs(i); } } puts("-1"); return 0; }