結果
問題 | No.2780 The Bottle Imp |
ユーザー |
|
提出日時 | 2024-06-07 21:55:45 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 2,803 bytes |
コンパイル時間 | 2,596 ms |
コンパイル使用メモリ | 215,808 KB |
実行使用メモリ | 32,968 KB |
最終ジャッジ日時 | 2024-12-27 13:44:39 |
合計ジャッジ時間 | 5,141 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;struct SCC {int n, group_num;std::vector<std::vector<int>> &g;std::vector<int> ids;SCC(std::vector<std::vector<int>> &_g) : n(_g.size()), g(_g), ids(n), group_num(0) {int now_ord = 0;std::vector<int> visited, low(n), ord(n, -1);visited.reserve(n);auto dfs = [&](auto self, int v) -> void {low[v] = ord[v] = now_ord++;visited.emplace_back(v);for(auto to : g[v]) {if (ord[to] == -1) {self(self, to);low[v] = std::min(low[v], low[to]);} else {low[v] = std::min(low[v], ord[to]);}}if (low[v] == ord[v]) {while (true) {int u = visited.back();visited.pop_back();ord[u] = n;ids[u] = group_num;if (u == v) break;}group_num++;}};for (int i = 0; i < n; i++) {if (ord[i] == -1) dfs(dfs, i);}for (auto& x : ids) {x = group_num - 1 - x;}}const int operator[](int p) const {assert(0 <= p && p < n);return ids[p];}int operator[](int p) {assert(0 <= p && p < n);return ids[p];}std::vector<std::vector<int>> groups(){std::vector<int> counts(group_num);for (auto x : ids) counts[x]++;std::vector<std::vector<int>> groups(group_num);for (int i = 0; i < group_num; i++) {groups[i].reserve(counts[i]);}for (int i = 0; i < n; i++) {groups[ids[i]].emplace_back(i);}return groups;}};int main(){ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;vector<vector<int>> g(n);for(int i = 0; i < n; i++){int m, j;cin >> m;while(m--){cin >> j;g[i].push_back(j - 1);}}SCC scc(g);auto G = scc.groups();vector<vector<int>> g2(G.size());vector<int> cnt(G.size());for(int i = 0; i < G.size(); i++){for(auto &&v : G[i]){for(auto &&u : g[v]){if(scc[v] == scc[u]) continue;g2[scc[v]].push_back(scc[u]);cnt[scc[u]]++;}}}if(cnt[scc[0]] != 0){cout << "No\n";return 0;}vector<bool> used(G.size());queue<int> que;que.emplace(scc[0]);while(!que.empty()){int v = que.front();if(que.size() >= 2){cout << "No\n";return 0;}used[v] = true;que.pop();for(auto &&u : g2[v]){cnt[u]--;if(cnt[u] == 0) que.emplace(u);}}cout << (count(used.begin(), used.end(), true) == G.size() ? "Yes" : "No") << '\n';}