結果

問題 No.1865 Make Cycle
ユーザー niuezniuez
提出日時 2022-03-04 23:08:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 343 ms / 3,000 ms
コード長 3,303 bytes
コンパイル時間 2,428 ms
コンパイル使用メモリ 214,792 KB
実行使用メモリ 13,692 KB
最終ジャッジ日時 2023-09-26 02:23:09
合計ジャッジ時間 7,550 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 186 ms
10,964 KB
testcase_01 AC 131 ms
9,024 KB
testcase_02 AC 218 ms
12,936 KB
testcase_03 AC 140 ms
10,152 KB
testcase_04 AC 212 ms
12,652 KB
testcase_05 AC 56 ms
13,272 KB
testcase_06 AC 174 ms
11,712 KB
testcase_07 AC 181 ms
10,292 KB
testcase_08 AC 237 ms
13,000 KB
testcase_09 AC 52 ms
12,180 KB
testcase_10 AC 210 ms
13,496 KB
testcase_11 AC 191 ms
12,980 KB
testcase_12 AC 178 ms
11,616 KB
testcase_13 AC 182 ms
10,844 KB
testcase_14 AC 144 ms
9,708 KB
testcase_15 AC 233 ms
12,168 KB
testcase_16 AC 256 ms
13,572 KB
testcase_17 AC 53 ms
9,868 KB
testcase_18 AC 58 ms
13,044 KB
testcase_19 AC 343 ms
13,692 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define STRINGIFY(n) #n
#define TOSTRING(n) STRINGIFY(n)
#define PREFIX "#" TOSTRING(__LINE__) "| "
#define debug(x) \
{ \
  std::cout << PREFIX << #x << " = " << x << std::endl; \
}
std::ostream& output_indent(std::ostream& os, int ind) {
  for(int i = 0; i < ind; i++) os << " ";
  return os;
}
template<class S, class T> std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p);
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<class S, class T> std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p) {
  return (os << "(" << p.first << ", " << p.second << ")");
}
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << "[";
  for(int i = 0;i < v.size();i++) os << v[i] << ", ";
  return (os << "]");
}
template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) { return std::vector<T>(n, std::forward<T>(val)); }
template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}
template<class Cond> struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  template<class T> bool operator()(T& a, const T& b) const { if(cond(a, b)) { a = b; return true; } return false; }
};
template<class Cond> chain<Cond> make_chain(Cond cond) { return chain<Cond>(cond); }

struct strongly_connected_componects {
  int n;
  std::vector<std::vector<pair<int, int>>> G;
  std::vector<std::vector<int>> scc;
  std::vector<int> low;
  std::vector<int> num;
  std::vector<int> st;
  std::vector<bool> in_st;
  int cnt;

  strongly_connected_componects(int n):
    n(n), G(n) {}

  void add_edge(int a, int b, int i) {
    G[a].emplace_back(b, i);
  }

  void visit(int v, int e) {
    low[v] = num[v] = ++cnt;
    st.emplace_back(v);
    in_st[v] = true;

    for(auto [t, ei]: G[v]) {
      if(ei >= e) continue;
      if(num[t] == 0) {
        visit(t, e);
        low[v] = std::min(low[v], low[t]);
      }
      else if(in_st[t]) {
        low[v] = std::min(low[v], num[t]);
      }
    }

    if(low[v] == num[v]) {
      std::vector<int> vs;
      while(true) {
        int t = st.back();
        st.pop_back();
        in_st[t] = false;
        vs.emplace_back(t);
        if(v == t) break;
      }
      scc.emplace_back(std::move(vs));
    }
  }

  void build_scc(int e) {
    low.assign(n, 0);
    num.assign(n, 0);
    st.clear();
    st.reserve(n);
    in_st.assign(n, false);
    scc.clear();
    cnt = 0;
    for(int i = 0;i < n;i++) {
      if(num[i] == 0) {
        visit(i, e);
      }
    }
  }
};



int main() {
  i64 N, Q;
  cin >> N >> Q;
  strongly_connected_componects scc(N);
  rep(i,0,Q) {
    i64 a, b;
    cin >> a >> b;
    a--;
    b--;
    scc.add_edge(a, b, i);
  }
  scc.build_scc(Q);
  if(scc.scc.size() == N) {
    cout << -1 << endl;
    return 0;
  }
  i64 ok = Q;
  i64 ng = 0;
  while(ok - ng > 1) {
    i64 mid = (ok + ng) / 2;
    scc.build_scc(mid);
    if(scc.scc.size() == N) {
      ng = mid;
    }
    else {
      ok = mid;
    }
  }
  cout << ok << endl;
}
0