結果

問題 No.2780 The Bottle Imp
ユーザー soto800
提出日時 2024-06-07 23:20:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 7,543 bytes
コンパイル時間 4,629 ms
コンパイル使用メモリ 267,228 KB
最終ジャッジ日時 2025-02-21 20:36:07
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 39 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;

#define lli long long int
#define REP(i, s, n) for (lli i = s; i < n; i++)
#define INF (1LL << 62)
#define mp(a, b) make_pair(a, b)
#define SORT(V) sort(V.begin(), V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) #VariableName
#define LOG1(x)                                                                \
  if (DEBUG)                                                                   \
    cout << TO_STRING(x) << "=" << x << " " << endl;
#define LOG2(x, y)                                                             \
  if (DEBUG)                                                                   \
    cout << TO_STRING(x) << "=" << x << " " << TO_STRING(y) << "=" << y << endl;
#define LOG3(x, y, z)                                                          \
  if (DEBUG)                                                                   \
    cout << TO_STRING(x) << "=" << x << " " << TO_STRING(y) << "=" << y << " " \
         << TO_STRING(z) << "=" << z << endl;
#define LOG4(w, x, y, z)                                                       \
  if (DEBUG)                                                                   \
    cout << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x << " " \
         << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z        \
         << endl;
#define LOG5(w, x, y, z, a)                                                    \
  if (DEBUG)                                                                   \
    cout << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x << " " \
         << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z << " " \
         << TO_STRING(a) << "=" << a << endl;
#define LOG6(w, x, y, z, a, b)                                                 \
  if (DEBUG)                                                                   \
    cout << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x << " " \
         << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z << " " \
         << TO_STRING(a) << "=" << a << " " << TO_STRING(b) << "=" << b        \
         << endl;

#define overload6(a, b, c, d, e, f, g, ...) g
#define LOG(...)                                                               \
  overload6(__VA_ARGS__, LOG6, LOG5, LOG4, LOG3, LOG2, LOG1)(__VA_ARGS__)

template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

mt19937 engine;
std::chrono::system_clock::time_point start, endTime;

std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}

__int128 parse(string &s) {
  __int128 ret = 0;
  for (int i = 0; i < s.length(); i++) {
    if ('0' <= s[i] && s[i] <= '9') {
      ret = 10 * ret + s[i] - '0';
    }
  }
  return ret;
}

template <typename T = int> struct Edge {
  int from, to;
  T cost;
  int idx;

  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1)
      : from(from), to(to), cost(cost), idx(idx) {}

  operator int() const { return to; }
};

template <typename T = int> struct Graph {
  vector<vector<Edge<T>>> g;
  int es;

  Graph() = default;

  explicit Graph(int n) : g(n), es(0) {}

  size_t size() const { return g.size(); }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es++);
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }

  void read(int M, int padding = -1, bool weighted = false,
            bool directed = false) {
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if (weighted)
        cin >> c;
      if (directed)
        add_directed_edge(a, b, c);
      else
        add_edge(a, b, c);
    }
  }

  inline vector<Edge<T>> &operator[](const int &k) { return g[k]; }

  inline const vector<Edge<T>> &operator[](const int &k) const { return g[k]; }
};

template <typename T = int> using Edges = vector<Edge<T>>;
template <typename T = int> struct StronglyConnectedComponents : Graph<T> {
public:
  using Graph<T>::Graph;
  using Graph<T>::g;
  vector<int> comp;
  Graph<T> dag;
  vector<vector<int>> group;

  void build() {
    rg = Graph<T>(g.size());
    for (size_t i = 0; i < g.size(); i++) {
      for (auto &e : g[i]) {
        rg.add_directed_edge(e.to, e.from, e.cost);
      }
    }
    comp.assign(g.size(), -1);
    used.assign(g.size(), 0);
    for (size_t i = 0; i < g.size(); i++)
      dfs(i);
    reverse(begin(order), end(order));
    int ptr = 0;
    for (int i : order)
      if (comp[i] == -1)
        rdfs(i, ptr), ptr++;
    dag = Graph<T>(ptr);
    for (size_t i = 0; i < g.size(); i++) {
      for (auto &e : g[i]) {
        int x = comp[e.from], y = comp[e.to];
        if (x == y)
          continue;
        dag.add_directed_edge(x, y, e.cost);
      }
    }
    group.resize(ptr);
    for (size_t i = 0; i < g.size(); i++) {
      group[comp[i]].emplace_back(i);
    }
  }

  int operator[](int k) const { return comp[k]; }

private:
  vector<int> order, used;
  Graph<T> rg;

  void dfs(int idx) {
    if (exchange(used[idx], true))
      return;
    for (auto &to : g[idx])
      dfs(to);
    order.push_back(idx);
  }

  void rdfs(int idx, int cnt) {
    if (comp[idx] != -1)
      return;
    comp[idx] = cnt;
    for (auto &to : rg.g[idx])
      rdfs(to, cnt);
  }
};

#define DEBUG 0

void solve() {
  //  write your code here

  lli N;
  cin >> N;

  StronglyConnectedComponents<lli> scc(N);

  REP(i, 0, N) {
    lli M;
    cin >> M;
    REP(j, 0, M) {
      lli a;
      cin >> a;
      a--;
      scc.add_directed_edge(i, a);
    }
  }
  scc.build();

  //自分を指す人がいない箇所から、DFSをして、最後まで行ったときに全点に到達していればよい

  auto nowScc = scc.dag;
  if (DEBUG) {
    REP(i, 0, nowScc.size()) {
      cout << i << " : ";
      for (auto e : nowScc[i]) {
        cout << e << " ";
      }
      cout << endl;
    }
  }

  int startNum = scc.comp[0];
  set<lli> visited;
  lli nowNum = startNum;
  while (true) {
    LOG(nowNum, nowScc.size(), nowScc[nowNum].size());
    visited.insert(nowNum);
    LOG(nowNum);
    if (visited.size() == nowScc.size()) {
      cout << "Yes" << endl;
      return;
    }
    set<lli> targets;
    for (auto e : nowScc[nowNum]) {
      targets.insert(e);
    }
    if (targets.size() == 0) {
      cout << "No" << endl;
      return;
    }
    if (targets.size() >= 2) {
      cout << "No" << endl;
      return;
    }
    nowNum = *targets.begin();
  }
}

// Generated by 2.13.0 https://github.com/kyuridenamida/atcoder-tools  (tips:
// You use the default template now. You can remove this line by using your
// custom template)
int main() {
  // Failed to predict input format

  lli N = 1;
  // cin >> N;
  while (N--)
    solve();

  return 0;
}
0