#986884 (C++23) No.2780 The Bottle Imp

• 問題: No.2780 The Bottle Imp
• ユーザー: Dương Nguyễn Cảnh
• 提出日時: 2024-06-07 22:19:19
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 8,834 bytes
• コンパイル時間: 4,698 ms
• コンパイル使用メモリ: 273,348 KB
• 実行使用メモリ: 45,856 KB
• 最終ジャッジ日時: 2024-12-27 13:59:08
• 合計ジャッジ時間: 6,558 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 39 WA * 1

ソースコード

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

template<class T>
struct graph{
    using Weight_t = T;
    struct Edge_t{
        int from, to;
        T cost;
    };
    int n;
    vector<Edge_t> edge;
    vector<vector<int>> adj;
    function<bool(int)> ignore;
    graph(int n = 1): n(n), adj(n){
        assert(n >= 1);
    }
    graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
        assert(n >= 1);
        if(undirected){
            for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
        }
        else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
    }
    graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
        assert(n >= 1);
        if(undirected){
            for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
        }
        else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
    }
    graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
        assert(n >= 1);
        for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
    }
    graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
        assert(n >= 1);
        for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
    }
    int add_vertex(){
        adj.emplace_back();
        return n ++;
    }
    int operator()(int u, int id) const{
        #ifdef LOCAL
        assert(0 <= id && id < (int)edge.size());
        assert(edge[id].from == u || edge[id].to == u);
        #endif
        return u ^ edge[id].from ^ edge[id].to;
    }
    int link(int u, int v, T w = {}){ // insert an undirected edge
        int id = (int)edge.size();
        adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
        return id;
    }
    int orient(int u, int v, T w = {}){ // insert a directed edge
        int id = (int)edge.size();
        adj[u].push_back(id), edge.push_back({u, v, w});
        return id;
    }
    vector<int> neighbor(int u, int exclude = -1) const{
        vector<int> res;
        for(auto id: adj[u]){
            if(id == exclude || ignore && ignore(id)) continue;
            res.push_back(operator()(u, id));
        }
        return res;
    }
    void clear(){
        for(auto [u, v, w]: edge){
            adj[u].clear();
            adj[v].clear();
        }
        edge.clear();
        ignore = {};
    }
    graph transpose() const{ // the transpose of the directed graph
        graph res(n);
        for(auto id = 0; id < (int)edge.size(); ++ id){
            if(ignore && ignore(id)) continue;
            res.orient(edge[id].to, edge[id].from, edge[id].cost);
        }
        return res;
    }
    int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
        return (int)adj[u].size();
    }
    // The adjacency list is sorted for each vertex.
    vector<vector<int>> get_adjacency_list() const{
        vector<vector<int>> res(n);
        for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
            if(ignore && ignore(id)) continue;
            res[(*this)(u, id)].push_back(u);
        }
        return res;
    }
    void set_ignoration_rule(const function<bool(int)> &f){
        ignore = f;
    }
    void reset_ignoration_rule(){
        ignore = nullptr;
    }
    friend ostream &operator<<(ostream &out, const graph &g){
        for(auto id = 0; id < (int)g.edge.size(); ++ id){
            if(g.ignore && g.ignore(id)) continue;
            auto &e = g.edge[id];
            out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
        }
        return out;
    }
};

// Requires graph
struct strongly_connected_components{
    int n, attempt;
    vector<int> dp;
    vector<int> stack;
    vector<int> assigned;
    vector<int> was;
    // condensation descriptions
    vector<int> belongs; // vertex -> component
    vector<vector<int>> comp; // in topological order
    graph<int> condensation; // edge weights are the original edge id
    // strongly_connectsed_components(){ }
    strongly_connected_components(int n){ init(n); }
    template<class T>
    strongly_connected_components(const graph<T> &g){ init(g.n); run_all(g); }
    void init(int n){
        this->n = n;
        dp.assign(n, -1);
        stack.reserve(n);
        assigned.assign(n, -1);
        was.assign(n, -2);
        attempt = -1;
        belongs.assign(n, -1);
        comp.clear();
    }
    // O(n + m) where n and m are the number of reachable nodes and edges respectively.
    template<class T>
    void _run(const graph<T> &g, const vector<int> &src){
        int it = 0;
        auto dfs = [&](auto self, int u)->int{
            int low = dp[u] = ++ it;
            was[u] = attempt;
            stack.push_back(u);
            for(auto id: g.adj[u]){
                if(g.ignore && g.ignore(id)) continue;
                int v = g.edge[id].to;
                if(assigned[v] != attempt){
                    if(was[v] != attempt){
                        was[v] = attempt;
                        dp[v] = -1;
                    }
                    low = min(low, ~dp[v] ? dp[v] : self(self, v));
                }
            }
            if(low == dp[u]){
                vector<int> c;
                while(true){
                    int v = stack.back();
                    stack.pop_back();
                    assigned[v] = attempt;
                    c.push_back(v);
                    if(u == v) break;
                }
                comp.push_back(move(c));
            }
            return dp[u] = low;
        };
        for(auto u: src) if(was[u] != attempt) dfs(dfs, u);
        reverse(comp.begin(), comp.end());
        condensation = {count()};
        for(auto i = 0; i < count(); ++ i) for(auto u: comp[i]) belongs[u] = i;
        for(auto i = 0; i < count(); ++ i) for(auto u: comp[i]) for(auto id: g.adj[u]){
            if(g.ignore && g.ignore(id)) continue;
            int v = g(u, id);
            if(i != belongs[v]){
                assert(i < belongs[v]);
                condensation.orient(i, belongs[v], id);
            }
        }
    }
    template<class T>
    void run(const graph<T> &g, const vector<int> &src){
        assert(g.n <= n);
        for(auto u: src) assert(0 <= u && u < g.n);
        comp.clear();
        ++ attempt;
        _run(g, src);
    }
    template<class T>
    void run_all(const graph<T> &g){
        assert(g.n <= n);
        comp.clear();
        ++ attempt;
        vector<int> src(n);
        iota(src.begin(), src.end(), 0);
        _run(g, src);
    }
    // Check if u is visited during the last run-like call
    bool visited(int u) const{
        assert(0 <= u && u < n);
        return was[u] == attempt;
    }
    // # of strongly connected components
    int count() const{
        return (int)comp.size();
    }
};

void solve() {
    int n;
    cin >> n;

    graph<int> g(n);
    for (int i = 0; i < n; ++i) {
        int cnt;
        cin >> cnt;
        while (cnt--) {
            int val; cin >> val;
            g.orient(i, --val);
        }
    }

    strongly_connected_components scc(g);

    int cnt = scc.count();
    bool res = true;
    g = scc.condensation;
    auto dfs = [&](auto self, int v) -> void {
        --cnt;
        if (g.degree(v) == 0) return;
        set<int> s;
        for (auto id : g.adj[v]) s.insert(g(v, id));
        if (isz(s) > 1) {
            res = false;
            return;
        }
        self(self, g(v, g.adj[v][0]));
    };
    dfs(dfs, scc.belongs[0]);
    res &= (cnt == 0);

    cout << (res ? "Yes" : "No") << endl;
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}