結果
問題 | No.1865 Make Cycle |
ユーザー |
|
提出日時 | 2022-03-16 00:13:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 250 ms / 3,000 ms |
コード長 | 1,537 bytes |
コンパイル時間 | 1,483 ms |
コンパイル使用メモリ | 137,448 KB |
最終ジャッジ日時 | 2025-01-28 09:48:37 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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;std::vector<std::vector<int>> graph(n);for (int e = 0; e < mid; ++e) {const auto [a, b] = edges[e];graph[a].push_back(b);}if (is_dag(graph)) {min = mid + 1;}else {max = mid;}}if (max <= q) {std::cout << max << '\n';}else {std::cout << "-1\n";}}