結果
問題 |
No.1865 Make Cycle
|
ユーザー |
|
提出日時 | 2022-03-16 00:12:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 168 ms / 3,000 ms |
コード長 | 1,615 bytes |
コンパイル時間 | 1,583 ms |
コンパイル使用メモリ | 137,916 KB |
最終ジャッジ日時 | 2025-01-28 09:48:27 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include <iostream> #include <unordered_map> #include <unordered_set> #include <set> #include <vector> #include <numeric> #include <algorithm> #include <queue> #include <string> #include <random> #include <array> #include <climits> #include <map> #include <cassert> #include <stack> #include <iomanip> #include <cfloat> #include <bitset> #include <fstream> #include <chrono> bool is_dag(const std::vector<std::vector<int>>& graph) { const int n = graph.size(); std::vector<bool> visit(n, false), out(n, false); std::stack<int> stack; for (auto i = 0; i < n; ++i) { if (visit[i]) continue; stack.push(i); while (!stack.empty()) { const auto current = stack.top(); stack.pop(); if (current >= 0) { if (visit[current]) { if (!out[current]) return false; continue; } visit[current] = true; stack.push(-1 - current); for (const auto next : graph[current]) { stack.push(next); } } else { out[-1 - current] = true; } } } return true; } int main() { int n, q; std::cin >> n >> q; std::vector<std::pair<int, int>> edges(q); for (auto& [a, b] : edges) { std::cin >> a >> b; --a; --b; } int min = 1; int max = q + 1; while (min < max) { auto mid = (min + max) >> 1; int e = 0; std::vector<std::vector<int>> graph(n); while (e < mid && min < max) { for (; e < mid; ++e) { const auto [a, b] = edges[e]; graph[a].push_back(b); } if (is_dag(graph)) { min = mid + 1; } else { max = mid; } mid = (min + max) >> 1; } } if (max <= q) { std::cout << max << '\n'; } else { std::cout << "-1\n"; } }