Submit Info #48235

Problem Lang User Status Time Memory
Cycle Detection cpp BigBag AC 90 ms 26.34 MiB

ケース詳細
Name Status Time Memory
example_00 AC 7 ms 12.30 MiB
example_01 AC 8 ms 12.21 MiB
example_02 AC 9 ms 12.20 MiB
random_00 AC 66 ms 25.15 MiB
random_01 AC 90 ms 26.34 MiB
random_02 AC 39 ms 18.21 MiB
random_03 AC 16 ms 17.78 MiB
random_04 AC 30 ms 17.97 MiB
random_05 AC 60 ms 23.34 MiB
random_06 AC 64 ms 23.18 MiB
random_07 AC 11 ms 13.71 MiB
random_08 AC 49 ms 21.43 MiB
random_09 AC 27 ms 16.80 MiB
random_dag_00 AC 83 ms 24.54 MiB
random_dag_01 AC 89 ms 25.85 MiB
random_dag_02 AC 41 ms 18.30 MiB
random_dag_03 AC 18 ms 17.80 MiB
random_dag_04 AC 27 ms 17.93 MiB
random_dag_05 AC 76 ms 23.18 MiB
random_dag_06 AC 59 ms 22.93 MiB
random_dag_07 AC 10 ms 13.68 MiB
random_dag_08 AC 58 ms 21.05 MiB
random_dag_09 AC 32 ms 16.80 MiB
random_dag_dense_00 AC 18 ms 17.30 MiB
random_dag_dense_01 AC 19 ms 16.68 MiB
random_dag_dense_02 AC 16 ms 17.10 MiB
random_dag_dense_03 AC 19 ms 16.83 MiB
random_dag_dense_04 AC 17 ms 17.71 MiB
random_dense_00 AC 19 ms 18.30 MiB
random_dense_01 AC 19 ms 17.80 MiB
random_dense_02 AC 16 ms 17.49 MiB
random_dense_03 AC 21 ms 18.11 MiB
random_dense_04 AC 18 ms 16.93 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]; vector<pair<int, int>> g[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[u].push_back({v, i}); //g.add_edge(u, v); } //g.prepare(); for (int i = 0; i < n; ++i) { if (!used[i]) { dfs(i); } } puts("-1"); return 0; }