結果

問題 No.2780 The Bottle Imp
コンテスト
ユーザー ooaiu
提出日時 2025-07-10 02:52:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 52 ms / 2,000 ms
コード長 852 bytes
コンパイル時間 4,394 ms
コンパイル使用メモリ 287,228 KB
実行使用メモリ 29,712 KB
最終ジャッジ日時 2025-07-10 02:52:18
合計ジャッジ時間 6,391 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/scc>
using namespace std;
using ll = long long;
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int N;
	cin >> N;
	atcoder::scc_graph G(N);
	vector<vector<int>> H(N);
	for(int i = 0; i < N; i++) {
		int m;
		cin >> m;
		while(m--) {
			int a;
			cin >> a;
			a--;
			G.add_edge(i, a);
			H[i].push_back(a);
		}
	}
	auto scc = G.scc();
	bool ok = false;
	for(int x: scc[0]) if(x == 0) ok = true;
	vector<int> idx(N);
	for(int i = 0; i < scc.size(); i++) for(int x: scc[i]) idx[x] = i;
	vector<int> T(scc.size() - 1);
	for(int i = 0; i < scc.size(); i++) for(int x: scc[i]) for(int y:H[x]) if(idx[y] == i + 1) T[i] = 1;
	bool ok1 = true;
	for(int i = 0; i < scc.size() - 1; i++) if(!T[i]) ok1 = false;
	cout << (ok && ok1 ? "Yes\n" : "No\n");
	cerr << ok << " " << ok1 << endl;
}
0