#1158291 (C++23) No.3508 OR Mapping

• 問題: No.3508 OR Mapping
• ユーザー: テナガザル
• 提出日時: 2026-04-17 22:47:26
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 730 ms / 2,000 ms
• コード長: 2,672 bytes
• コンパイル時間: 2,290 ms
• コンパイル使用メモリ: 185,744 KB
• 実行使用メモリ: 134,248 KB
• 最終ジャッジ日時: 2026-04-17 22:48:06
• 合計ジャッジ時間: 26,858 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 65

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> g(n);
  for (int i = 0; i < m; ++i)
  {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
  }
  vector<int> p, check(n);
  auto dfs = [&](auto f, int now) -> void
  {
    if (check[now]) return;
    check[now] = 1;
    for (auto to : g[now]) f(f, to);
    p.push_back(now);
  };
  for (int i = 0; i < n; ++i) dfs(dfs, i);
  vector<vector<int>> gr;
  vector<int> id(n);
  int gsiz = 0;
  {
    vector<vector<int>> rg(n);
    for (int i = 0; i < n; ++i)
    {
      for (auto to : g[i]) rg[to].push_back(i);
    }
    check.assign(n, 0);
    auto dfs2 = [&](auto f, int now) -> void
    {
      if (check[now]) return;
      check[now] = 1;
      gr.back().push_back(now);
      id[now] = gsiz;
      for (auto to : rg[now]) f(f, to);
    };
    for (int i = n - 1; i >= 0; --i)
    {
      if (!check[p[i]])
      {
        gr.push_back({});
        dfs2(dfs2, p[i]);
        ++gsiz;
      }
    }
  }
  // for (int i = 0; i < gsiz; ++i)
  // {
  //   cout << i << ":";
  //   for (auto to : gr[i]) cout << ' ' << to;
  //   cout << endl;
  // }
  check.assign(gsiz, 0);
  for (int i = 0; i < n; ++i)
  {
    for (auto to : g[i])
    {
      if (id[to] == id[i] + 1) check[id[i]] = 1;
    }
  }
  for (int i = 0; i < gsiz - 1; ++i) if (!check[i])
  {
    cout << "No" << endl;
    return 0;
  }
  vector<vector<vector<int>>> grg(gsiz);
  vector<int> idg(n);
  for (int i = 0; i < gsiz; ++i)
  {
    for (int j = 0; j < gr[i].size(); ++j)
    {
      idg[gr[i][j]] = j;
    }
  }
  auto cal = [](vector<vector<int>> &g) -> int
  {
    int n = g.size();
    if (n == 1) return 0;
    vector<int> d[2];
    for (int i = 0; i < 2; ++i) d[i].resize(n);
    auto dfs = [&](auto f, int now, int b) -> void
    {
      if (d[b][now]) return;
      d[b][now] = 1;
      for (auto to : g[now]) f(f, to, 1 ^ b);
    };
    dfs(dfs, 0, 0);
    int ret = 1;
    for (int i = 0; i < 2; ++i) for (int j = 0; j < n; ++j) if (!d[i][j]) ret = -1;
    return ret;
  };
  check.assign(gsiz, 0);
  for (int i = 0; i < gsiz; ++i)
  {
    grg[i].resize(gr[i].size());
    for (auto v : gr[i])
    {
      for (auto to : g[v])
      {
        if (id[v] == id[to])
        {
          grg[i][idg[v]].push_back(idg[to]);
        }
      }
    }
    check[i] = cal(grg[i]);
  }
  int ans = check[0];
  if (id[0] > 0) ans = -1;
  for (int i = 1; i < gsiz; ++i)
  {
    if (check[i] == -1) ans = -1;
    else if (check[i] == 0)
    {
      if (check[i - 1] != 1) ans = 0;
    }
  }
  cout << (ans == 1 ? "Yes" : "No") << endl;
}