結果

問題 No.3508 OR Mapping
コンテスト
ユーザー AK_Mi
提出日時 2026-04-18 19:07:37
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,819 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,745 ms
コンパイル使用メモリ 353,304 KB
実行使用メモリ 167,604 KB
最終ジャッジ日時 2026-04-18 19:08:01
合計ジャッジ時間 20,308 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 49 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
//using mint = modint998244353;
void dfs(ll x, vector<vector<ll>> &pass, vector<bool> &come, vector<ll> &p){
    for(ll i : pass[x]){
        if(come[i])continue;
        come[i] = 1;
        dfs(i,pass,come,p);
    }
    p.push_back(x);
}
void rdfs(ll x, vector<vector<ll>> &rpass, vector<bool> &rcome, vector<ll> &list){
    for(ll i : rpass[x]){
        if(rcome[i])continue;
        rcome[i] = 1;
        list.push_back(i);
        rdfs(i,rpass,rcome,list);
    }
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    ll n,m,k;
    cin >> n >> m >> k;

    vector<vector<ll>> pass(n,vector<ll>(0));
    vector<vector<ll>> rpass(n,vector<ll>(0));
    vector<bool> come(n,0);
    vector<bool> rcome(n,0);
    vector<ll> p(0);
    vector<vector<ll>> css(0);
    vector<ll> wh(n,-1);
    ll u,v;
    for(ll i = 0; i < m; i++){
        cin >> u >> v;
        u--;
        v--;
        pass[u].push_back(v);
        rpass[v].push_back(u);
    }

    for(ll i = 0; i < n; i++){
        if(come[i])continue;
        come[i] = 1;
        dfs(i,pass,come,p);
    }

    reverse(p.begin(),p.end());

    for(ll i = 0; i < n; i++){
        if(rcome[p[i]])continue;
        rcome[p[i]] = 1;
        vector<ll> list = {p[i]};
        rdfs(i,rpass,rcome,list);
        for(ll t : list){
            wh[t] = css.size();
        }
        css.push_back({list});
    }

///////////////////CSS////////////////////////////

    ll siz = css.size();
    bool ans = 1;
    if(wh[0] != 0)ans = 0;
    for(ll i = 0; i < siz-1; i++){
        if(css[i].size() * css[i+1].size() == 1)ans = 0;
        bool ok = 0;
        for(ll t : css[i]){
            for(ll j : pass[t]){
                if(wh[j] == i+1){
                    ok = 1;
                    break;
                }
            }
            if(ok)break;
        }
        if(!ok){
            ans = 0;
            break;
        }
    }

    queue<pair<ll,ll>> bfs;
    vector<vector<bool>> dp(n,vector<bool>(2,0));
    for(ll i = 0; i < siz; i++){
        if(css[i].size() == 1)continue;
        bfs.push({css[i][0],0});
        dp[css[i][0]][0] = 1;
        while(!bfs.empty()){
            ll x = bfs.front().first;
            ll q = bfs.front().second;
            bfs.pop();
            for(ll t : pass[x]){
                ll nq = q * -1 + 1;
                if(wh[t] != i)continue;
                if(dp[t][nq])continue;
                dp[t][nq] = 1;
                bfs.push({t,nq});
            }
        }
        if(!dp[css[i][0]][1]){
            ans = 0;
            break;
        }
    }

    if(ans)cout << "Yes" << '\n';
    else cout << "No" << '\n';

}
0