結果
問題 | No.2780 The Bottle Imp |
ユーザー |
![]() |
提出日時 | 2024-06-07 22:50:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 3,228 bytes |
コンパイル時間 | 6,215 ms |
コンパイル使用メモリ | 319,996 KB |
実行使用メモリ | 34,960 KB |
最終ジャッジ日時 | 2024-12-27 14:18:27 |
合計ジャッジ時間 | 8,336 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using mint = atcoder::modint1000000007;istream& operator>>(istream& is, mint& a) {int t; is >> t; a = t;return is;}ostream& operator<<(ostream& os, mint a) {return os << a.val();}#endif#ifdef DEBUG#define _GLIBCXX_DEBUG#else#pragma GCC target("avx2")#pragma GCC optimize("Ofast,unroll-loops")#define cerr if (false) cerr#undef assert#define assert(...) void(0)// #undef endl// #define endl '\n'#endif#undef long#define long long long#define overload3(a, b, c, name, ...) name#define rep1(n) for (long i = 0; i < n; i++)#define rep2(i, n) for (long i = 0; i < n; i++)#define rep3(i, a, b) for (long i = a; i < b; i++)#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)#define per1(n) for (long i = n - 1; i >= 0; i--)#define per2(i, n) for (long i = n - 1; i >= 0; i--)#define per3(i, a, b) for (long i = b - 1; i >= (a); i--)#define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)#define ALL(a) a.begin(), a.end()#define UNIQUE(a) sort(ALL(a)); a.erase(unique(ALL(a)), a.end())#define vec vectortemplate<typename T>ostream& operator<<(ostream& os, vector<T> a) {const int n = a.size();rep(i, n) {os << a[i];if (i + 1 != n) os << " ";}return os;}template<typename T, size_t n>ostream& operator<<(ostream& os, array<T, n> a) {rep(i, n) {os << a[i];if (i + 1 != n) os << " ";}return os;}template<typename T>istream& operator>>(istream& is, vector<T>& a) {for (T& i : a) is >> i;return is;}template<typename T, typename S>bool chmin(T& x, S y) {if (x > (T)y) { x = (T)y; return true; }return false;}template<typename T, typename S>bool chmax(T& x, S y) {if (x < (T)y) { x = (T)y; return true; }return false;}template<typename T>void operator++(vector<T>& a) {for (T& i : a) ++i;}template<typename T>void operator--(vector<T>& a) {for (T& i : a) --i;}template<typename T>void operator++(vector<T>& a, int) {for (T& i : a) i++;}template<typename T>void operator--(vector<T>& a, int) {for (T& i : a) i--;}void solve() {int n; cin >> n;atcoder::scc_graph g(n);vec<vec<int>> ggg(n);rep(i, n) {int m; cin >> m;rep(j, m) {int a; cin >> a; a--;g.add_edge(i, a);ggg[i].push_back(a);}}auto scc = g.scc();vec<int> s(n);int m = scc.size();rep(i, m) for (int j : scc[i]) s[j] = i;if (m != 1 && s[0] != 0) {cout << "No" << endl;return;}vec<vec<int>> gg(m);rep(i, n) for (int j : ggg[i]) if (s[i] != s[j]) gg[s[i]].push_back(s[j]);rep(i, m - 1) {bool ok = false;for (int j : gg[i]) ok |= j == i + 1;if (!ok) {cout << "No" << endl;return;}}cout << "Yes" << endl;return;}int main(){srand((unsigned)time(NULL));cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(40);int t = 1;// cin >> t;rep(t)solve();return 0;}