結果
問題 | No.2780 The Bottle Imp |
ユーザー |
|
提出日時 | 2024-06-07 22:20:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,533 bytes |
コンパイル時間 | 3,941 ms |
コンパイル使用メモリ | 278,600 KB |
実行使用メモリ | 42,400 KB |
最終ジャッジ日時 | 2024-12-27 14:00:51 |
合計ジャッジ時間 | 7,917 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 39 WA * 1 |
ソースコード
// github.com/Johniel/contests// yukicoder/2780/main.cpp#include <bits/stdc++.h>#define each(i, c) for (auto& i : c)#define unless(cond) if (!(cond))using namespace std;template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p);template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p);template<typename P, typename Q, typename R> ostream& operator << (ostream& os, tuple<P, Q, R> t) { os << "(" << get<0>(t) << "," << get<1>(t) << ","<< get<2>(t) << ")"; return os; }template<typename P, typename Q, typename R> istream& operator >> (istream& is, tuple<P, Q, R>& t) { is >> get<0>(t) >> get<1>(t) >> get<2>(t);return is; }template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "set{"; for (auto& i: s) os << i << ","; os << "}"; return os; }template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "map{"; for (auto& i: m) os << i << ","; os << "}"; returnos; }template<typename E, size_t N> istream& operator >> (istream& is, array<E, N>& a) { for (auto& i: a) is >> i; return is; }template<typename E, size_t N> ostream& operator << (ostream& os, array<E, N>& a) { os << "[" << N << "]{"; for (auto& i: a) os << i << ","; os <<"}"; return os; }template<typename T> ostream& operator << (ostream& os, stack<T> s) { os << "stack{"; while (s.size()) { os << s.top() << ","; s.pop(); } os << "}";return os; }template<typename T> ostream& operator << (ostream& os, queue<T> q) { os << "queue{"; while (q.size()) { os << q.front() << ","; q.pop(); } os << "}"; return os; }template<typename T> ostream& operator << (ostream& os, deque<T> q) { os << "deque{"; for (int i = 0; i < q.size(); ++i) os << q[i] << ","; os << "}"; return os; }template<typename T> ostream& operator << (ostream& os, priority_queue<T> q) { os << "heap{"; while (q.size()) { os << q.top() << ","; q.pop(); } os<< "}"; return os; }template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }__attribute__((constructor)) static void _____(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.setf(ios_base::fixed); cout.precision(15); return ; }using lli = long long int;using ull = unsigned long long;using str = string;template<typename T> using vec = vector<T>;namespace {// https://atcoder.jp/contests/typical90/tasks/typical90_uconst int N = 1e5 + 3;bool vis[N];void rec(vec<int> graph[N], int curr, int ord[], int &cnt){vis[curr] = true;for (auto& next : graph[curr]) {unless (vis[next]) rec(graph, next, ord, cnt);}ord[--cnt] = curr;return ;}vector<int> g[N];vector<int> h[N];void init(const int size){fill(g, g + size, vector<int>());}int ord[N];int scc[N];vector<vector<int>> detect_scc(const int size){int cnt, prev = size - 1;vector<vector<int>> ret;fill(ord, ord + size, -1);fill(scc, scc + size, -1);fill(h, h + size, vector<int>());for (int curr = 0; curr < size; ++curr) {for (const auto& next : g[curr]) {h[next].push_back(curr);}}cnt = size;fill(vis, vis + N, false);for (int i = 0; i < size; ++i) {unless (vis[i]) rec(g, i, ord, cnt);}cnt = size;fill(vis, vis + N, false);for (int i = 0; i < size; ++i) {unless (vis[ord[i]]) {rec(h, ord[i], scc, cnt);int j = prev;vector<int> T;for (j = prev; 0 <= j && scc[j] != -1; --j) T.push_back(scc[j]);prev = j;ret.push_back(T);}}return ret;}};int main(int argc, char *argv[]){int n;while (cin >> n) {init(n);vec<pair<int, int>> es;for (int i = 0; i < n; ++i) {int m;cin >> m;for (int j = 0; j < m; ++j) {int x;cin >> x;--x;g[i].push_back(x);es.push_back(make_pair(i, x));}}auto v = detect_scc(n);map<int, int> m;for (int i = 0; i < v.size(); ++i) {each (j, v[i]) m[j] = i;}decltype(es) u;each (e, es) {e.first = m[e.first];e.second = m[e.second];if (e.first != e.second) u.push_back(e);}sort(u.begin(), u.end());u.erase(unique(u.begin(), u.end()), u.end());fill(g, g + n, vec<int>());vec<int> rev[n];each (i, u) {g[i.first].push_back(i.second);rev[i.second].push_back(i.first);}n = v.size();vec<int> leaf;for (int i = 0; i < n; ++i) {if (g[i].empty()) leaf.push_back(i);}bool f = true;f = f && (leaf.size() <= 1);if (leaf.size()) {set<int> vis;int x = leaf.front();while (rev[x].size()) {vis.insert(x);x = rev[x].front();}vis.insert(x);f = f && (vis.size() == v.size() && m[0] == x);}cout << (f || (n == 1) ? "Yes" : "No") << endl;}return 0;}