結果
問題 | No.2780 The Bottle Imp |
ユーザー |
![]() |
提出日時 | 2024-06-07 22:12:09 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,360 bytes |
コンパイル時間 | 1,980 ms |
コンパイル使用メモリ | 139,460 KB |
実行使用メモリ | 40,232 KB |
最終ジャッジ日時 | 2024-12-27 13:52:33 |
合計ジャッジ時間 | 4,776 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 39 WA * 1 |
ソースコード
//#pragma GCC target("avx2")//#pragma GCC optimize("O3")//#pragma GCC optimize("unroll-loops")#include <algorithm>#include <bitset>#include <cassert>#include <cmath>#include <complex>#include <climits>#include <deque>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <set>#include <string>#include <tuple>#include <vector>using namespace std;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;using pli = pair<ll,int>;#define TEST cerr << "TEST" << endl#define AMARI 998244353//#define AMARI 1000000007#define el '\n'#define El '\n'// 強連結成分分解(SCC)周りを行うクラス// 再帰関数周りでグローバル変数使ったりが多いのでクラスでclass ococo_scc {private:void dfs(int a) {checked[a] = true;for(int i = 0; i < g[a].size(); i++) {if(!checked[g[a][i]]) {dfs(g[a][i]);}}junban[nj] = a;nj++;}void dfs2(int a) {vector<int> ans;checked[a] = true;kari.push_back(a);// cout << a << endl;for(int i = 0; i < g2[a].size(); i++) {if(!checked[g2[a][i]]) {dfs2(g2[a][i]);}}}public:vector<vector<int>> g;vector<vector<int>> g2;vector<bool> checked;vector<int> junban;int nj;int gsize;// N個のノードに初期化する O(N)void syokica(int n) {nj = 0;gsize = n;g.resize(n);g2.resize(n);checked.resize(n);junban.resize(n);for(int i = 0; i < n; i++) {g[i].resize(0);g2[i].resize(0);checked[i] = false;}}// a→bに向かう有向辺を追加する O(1)void einsert(int a, int b) {g[a].push_back(b);g2[b].push_back(a);}// 具体的な有向ループを求めるためのDFSを行う O(V+E)// 「あるループの成分が全て入ったvector」のvector が返り値vector<int> kari;vector<vector<int>> loop_kettei(void) {for(int i = 0; i < gsize; i++) {if(!checked[i]) dfs(i);}for(int i = 0; i < gsize; i++) checked[i] = false;vector<vector<int>> ans(0);for(int i = gsize - 1; i >= 0; i--) {if(!checked[junban[i]]) {kari.resize(0);dfs2(junban[i]);ans.push_back(kari);}}return ans;}};class ococo_unionfind {// できること// 点の挿入// その点の根を求める関数// 辺の挿入// 連結判定// 島が何個あるかの出力// それぞれの島について、何個の点があるかの出力public:ococo_unionfind(int n = 0) {for(int i = 0; i < n; i++) vinsert();}int simakosuu = 0;// g[i] = {その点の一個上の点,その点のrank}// その点のrank:その点の下に何個点があるか(上に何個あるかに変えた方がいいかも?)vector<pair<int, int>> g;// rs[i] = その点が含まれている連結成分に何個の点があるか// その連結成分の根について聞かないと返さないvector<int> rs;// 点の挿入 O(1)void vinsert(void) {g.emplace_back(g.size(), 1);simakosuu++;rs.push_back(1);}// ある点の根を求める関数 O(α(N))int ne(int a) {if(g[a].first == a) return a;else {return g[a].first = ne(g[a].first);}}// 辺の挿入 O(logN)void einsert(int a, int b) {if(a != b) {int a1 = ne(a), a2 = ne(b);if(a1 != a2) {simakosuu--;int rs12sum = rs[a1] + rs[a2];rs[a1] = rs12sum;rs[a2] = rs12sum;if(g[a1].second < g[a2].second) {g[a1].first = a2;g[a2].second = max(g[a1].second + 1, g[a2].second);} else {g[a2].first = a1;g[a1].second = max(g[a2].second + 1, g[a1].second);}}}}void peinsert(pair<int,int> p){einsert(p.first,p.second);return;}// 2つのノードが繋がっているか判定する関数 O(α(N))bool renketucheck(int a, int b) {if(ne(a) == ne(b)) return true;else return false;}bool prenketucheck(pair<int,int> p){return renketucheck(p.first,p.second);}// 何個の島に分かれているか出力する関数 O(1)int islandnum(void) {return simakosuu;}// ある点について、その点が含まれている連結成分が何個の点を持つか返す関数// O(α(N))int islandsize(int a) {return rs[ne(a)];}};#define MULTI_TEST_CASE falsevoid solve(void){//問題を見たらまず「この問題設定から言えること」をいっぱい言う//一個回答に繋がりそうな解法が見えても、実装や細かい詰めに時間がかかりそうなら別の方針を考えてみる//添え字回りで面倒になりそうなときは楽になる言い換えを実装の前にじっくり考える//ある程度考察しても全然取っ掛かりが見えないときは実験をしてみる//よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書くint n;cin >> n;vector<vector<int>> g(n);ococo_scc scc;scc.syokica(n);ococo_unionfind uf(n);for(int i = 0; i < n; i++){int m;cin >> m;while(m--){int idx;cin >> idx;idx--;g[i].push_back(idx);scc.einsert(i,idx);}}vector<vector<int>> scc_res = scc.loop_kettei();for(int i = 0; i < scc_res.size(); i++){for(int j = 0; j < (int)scc_res[i].size() - 1; j++){uf.einsert(scc_res[i][j],scc_res[i][j + 1]);}}vector<vector<int>> ng(n);for(int i = 0; i < n; i++){for(int j = 0; j < g[i].size(); j++){if(uf.ne(i) == uf.ne(g[i][j]))continue;ng[uf.ne(i)].push_back(uf.ne(g[i][j]));}}vector<int> hairu(n,0);for(int i = 0; i < n; i++){sort(ng[i].begin(),ng[i].end());ng[i].erase(unique(ng[i].begin(),ng[i].end()),ng[i].end());}queue<int> que;que.push(uf.ne(0));vector<bool> visited(n,false);while(!que.empty()){int fr = que.front();que.pop();visited[fr] = true;if(ng[fr].size() >= 2){cout << "No" << el;return;}if(ng[fr].size() == 1)que.push(ng[fr][0]);}for(int i = 0; i < n; i++){if(!visited[uf.ne(i)]){cout << "No" << el;return;}}cout << "Yes" << el;return;}void calc(void){return;}signed main(void){cin.tie(nullptr);ios::sync_with_stdio(false);calc();int t = 1;if(MULTI_TEST_CASE)cin >> t;while(t--){solve();}return 0;}