結果

問題 No.2780 The Bottle Imp
ユーザー ococonomy1ococonomy1
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//#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)
// vectorvector
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 false
void 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0