#1195613 (C++23(gcc16)) No.1023 Cyclic Tour

• 問題: No.1023 Cyclic Tour
• ユーザー: C
• 提出日時: 2026-10-27 23:39:23
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 85 ms / 2,000 ms
• コード長: 5,205 bytes
• コンパイル時間: 6,511 ms
• コンパイル使用メモリ: 400,932 KB
• 実行使用メモリ: 24,184 KB
• 最終ジャッジ日時: 2026-10-27 23:39:42
• 合計ジャッジ時間: 17,803 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
sample	AC * 4
other	AC * 49

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
using mint=modint1000000007;
// using mint2=static_modint<2>;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

#line 2 "graph/strongly-connected-components.hpp"

#line 2 "graph/graph-template.hpp"

template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph([[maybe_unused]] int N, int M, int is_weighted = true,
                 bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */
#line 4 "graph/strongly-connected-components.hpp"

// Strongly Connected Components
// DAG of SC graph   ... scc.dag (including multiedges)
// new node of k     ... scc[k]
// inv of scc[k] = i ... scc.belong(i)
template <typename G>
struct StronglyConnectedComponents {
 private:
  const G &g;
  vector<vector<int>> rg;
  vector<int> comp, order;
  vector<char> used;
  vector<vector<int>> blng;

 public:
  vector<vector<int>> dag;
  StronglyConnectedComponents(G &_g) : g(_g), used(g.size(), 0) { build(); }

  int operator[](int k) { return comp[k]; }

  vector<int> &belong(int i) { return blng[i]; }

 private:
  void dfs(int idx) {
    if (used[idx]) return;
    used[idx] = true;
    for (auto to : g[idx]) dfs(int(to));
    order.push_back(idx);
  }

  void rdfs(int idx, int cnt) {
    if (comp[idx] != -1) return;
    comp[idx] = cnt;
    for (int to : rg[idx]) rdfs(to, cnt);
  }

  void build() {
    for (int i = 0; i < (int)g.size(); i++) dfs(i);
    reverse(begin(order), end(order));
    used.clear();
    used.shrink_to_fit();

    comp.resize(g.size(), -1);

    rg.resize(g.size());
    for (int i = 0; i < (int)g.size(); i++) {
      for (auto e : g[i]) {
        rg[(int)e].emplace_back(i);
      }
    }
    int ptr = 0;
    for (int i : order)
      if (comp[i] == -1) rdfs(i, ptr), ptr++;
    rg.clear();
    rg.shrink_to_fit();
    order.clear();
    order.shrink_to_fit();

    dag.resize(ptr);
    blng.resize(ptr);
    for (int i = 0; i < (int)g.size(); i++) {
      blng[comp[i]].push_back(i);
      for (auto &to : g[i]) {
        int x = comp[i], y = comp[to];
        if (x == y) continue;
        dag[x].push_back(y);
      }
    }
  }
};

int main()
{
  	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	UnweightedGraph g(N);
	vector<pi>roads(M);
	for(auto& [a,b]:roads){
		int c;
		cin>>a>>b>>c;
		--a,--b;
		g[a].push_back(b);
		if(c==1)g[b].push_back(a);
	}
	StronglyConnectedComponents<UnweightedGraph>scc(g);
	vi nedges(scc.dag.size());
	for(auto [a,b]:roads){
		if(scc[a]==scc[b])nedges[scc[a]]++;
	}
	rep(i,0,scc.dag.size()){
		if(nedges[i]>=scc.belong(i).size()){
			cout<<"Yes\n";
			return 0;
		}
	}
	cout<<"No\n";
}