結果

問題 No.3508 OR Mapping
コンテスト
ユーザー The Forsaking
提出日時 2026-04-18 18:38:25
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 325 ms / 2,000 ms
コード長 2,271 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,979 ms
コンパイル使用メモリ 215,352 KB
実行使用メモリ 86,016 KB
最終ジャッジ日時 2026-04-18 18:38:42
合計ジャッジ時間 12,146 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
using ll = long long;
const int N = 2000010, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];

int e[N], ne[N], h[N], idx, k;
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
int dfn[N], low[N], stk[N], ts, top, scc_cnt, id[N], sz[N], color[N];
bool in_stk[N], f[N];

void tarjan(int r, int f)
{
    dfn[r] = low[r] = ++ts;
    stk[++top] = r, in_stk[r] = true;
    for (int i = h[r]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j, r);
            low[r] = min(low[r], low[j]);
        }
        else if (in_stk[j]) low[r] = min(low[r], dfn[j]);
    }
    
    if (dfn[r] == low[r])
    {
        int y;
        scc_cnt++;
        do {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt]++;
        } while (y != r);
    }
}

void dfs(int r, int c, int p) {
    color[r] = c;
    for (int i = h[r]; i != -1; i = ne[i]) {
        int j = e[i];
        if (id[j] != p) continue;
        if (!color[j]) dfs(j, 3 - c, p);
        else if (color[j] == color[r]) f[p] = 1;
    }
}

void solve() {
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, a, b; i < m + 1; i++) {
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    for (int i = 1; i < n + 1; i++)
        if (!dfn[i])
            tarjan(i, -1);
    for (int i = 1; i < n + 1; i++)
        if (!color[i])
            dfs(i, 1, id[i]);
    if (id[1] != scc_cnt) {
        puts("No");
        return;
    }
    vector<vector<int> > v(scc_cnt + 1);
    for (int i = 1; i < n + 1; i++) v[id[i]].push_back(i);
    for (int i = scc_cnt; i; i--) {
        bool flag = 0;
        for (auto u : v[i]) {
            for (int j = h[u]; ~j; j = ne[j]) {
                int k = e[j];
                flag |= id[k] == i - 1;
            }
        }
        if (i > 1 && !flag) {
            puts("No");
            return;
        }
        if (i != scc_cnt && f[i + 1] && sz[i] == 1) continue;
        if (!f[i]) {
            puts("No");
            return;
        }
    }
    puts("Yes");
}

int main() {
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}
0