結果
問題 |
No.1865 Make Cycle
|
ユーザー |
![]() |
提出日時 | 2022-03-05 04:05:41 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 859 ms / 3,000 ms |
コード長 | 1,316 bytes |
コンパイル時間 | 3,537 ms |
コンパイル使用メモリ | 146,612 KB |
実行使用メモリ | 18,012 KB |
最終ジャッジ日時 | 2024-07-19 03:30:16 |
合計ジャッジ時間 | 14,365 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; int N, Q; int A[100010]; int B[100010]; map<int, map<int, bool>> E; void update_edges(int x) { for (int i = 0; i < Q; ++i) { int a = A[i]; int b = B[i]; if (i < x) { E[a][b] = true; } else { E[a][b] = false; } } } bool dfs(int v, vector<int> &visited) { visited[v] = 1; for (auto &[u, s] : E[v]) { if (not s) continue; if (visited[u] == 1) return true; if (visited[u] == 0 && dfs(u, visited)) return true; } visited[v] = 2; return false; } bool has_cycle() { vector<int> visited(N + 1, 0); for (int v = 1; v <= N; ++v) { if (visited[v] == 0 && dfs(v, visited)) return true; } return false; } int main() { cin >> N >> Q; for (int i = 0; i < Q; ++i) { cin >> A[i] >> B[i]; } update_edges(Q); if (not has_cycle()) { cout << -1 << endl; return 0; } int ok = Q; int ng = 0; while (abs(ok - ng) >= 2) { int x = (ok + ng) / 2; update_edges(x); if (has_cycle()) { ok = x; } else { ng = x; } } cout << ok << endl; return 0; }