結果

問題 No.3291 K-step Navigation
コンテスト
ユーザー Aeren
提出日時 2025-10-03 22:28:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 155 ms / 3,000 ms
コード長 6,865 bytes
コンパイル時間 3,111 ms
コンパイル使用メモリ 297,304 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-03 23:30:43
合計ジャッジ時間 6,090 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #include <bits/allocator.h> // Temp fix for gcc13 global pragma
// #pragma GCC target("avx2,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
using namespace numbers;
#ifdef LOCAL
	#include "Debug.h"
#else
	#define debug_endl() 42
	#define debug(...) 42
	#define debug2(...) 42
	#define debug_bin(...) 42
#endif
// Returns the largest integer k with x >= k * y
template<class T, class U> U floor_div(T x, U y){
	assert(y > 0);
	return x / y - (x % y < 0);
}
// Returns the smallest integer k with x <= k * y
template<class T, class U> U ceil_div(T x, U y){
	assert(y > 0);
	return x / y + (x % y > 0);
}
template<class T> T &ctmin(T &x){ return x; }
template<class T, class Head, class ...Tail> T &ctmin(T &x, const Head &h, const Tail &... t){ return ctmin(x = min<T>(x, h), t...); }
template<class T> T &ctmax(T &x){ return x; }
template<class T, class Head, class ...Tail> T &ctmax(T &x, const Head &h, const Tail &... t){ return ctmax(x = max<T>(x, h), t...); }

// std::chunk_by cuz AtCoder is stuck on 3 years old gcc
vector<vector<int>> chunk_by(auto data, auto eq){
	vector<vector<int>> chunks;
	for(auto l = data.begin(); l != data.end(); ){
		auto r = next(l);
		vector<int> chunk{*l};
		while(r != data.end() && eq(*prev(r), *r)){
			chunk.push_back(*r);
			r = next(r);
		}
		chunks.push_back(chunk);
		l = r;
	}
	return chunks;
}

template<class T>
struct graph{
#ifdef LOCAL
	#define ASSERT(x) assert(x)
#else
	#define ASSERT(x) 42
#endif
	using Weight_t = T;
	struct Edge_t{
		int from, to;
		T cost;
		Edge_t &inplace_flip(){
			swap(from, to);
			return *this;
		}
		Edge_t flip() const{
			return (*this).inplace_flip();
		}
	};
	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, const 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, const 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{
		ASSERT(0 <= id && id < (int)edge.size());
		ASSERT(edge[id].from == u || edge[id].to == u);
		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;
	}
	auto neighbor(int u, int exclude = -1) const{
		return adj[u]
			| views::filter([this, u, exclude](int id){ return id != exclude && !(ignore && ignore(id)); })
			| views::transform([this, u](int id){ return (*this)(u, id); });
	}
	auto weighted_neighbor(int u, int exclude = -1) const{
		return adj[u]
			| views::filter([this, u, exclude](int id){ return id != exclude && !(ignore && ignore(id)); })
			| views::transform([this, u](int id){ return pair{(*this)(u, id), edge[id].cost}; });
	}
	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, bool include_ignored_edges = true) const{
		ASSERT(0 <= u && u < n);
		if(include_ignored_edges || !ignore) return (int)adj[u].size();
		else{
			int deg = 0;
			for(auto id: adj[u]) deg += !ignore(id);
			return deg;
		}
	}
	// 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;
	}
	template<class ostream>
	friend ostream &operator<<(ostream &out, const graph &g){
		out << "\n";
		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;
	}
	template<bool directed = false, bool has_weight = false>
	static graph read(int n, int m = -1, int offset = 1){
		ASSERT(n >= 1);
		if(m == -1) m = n - 1;
		ASSERT(m >= 0);
		graph<T> g(n);
		for(auto id = 0; id < m; ++ id){
			int u, v;
			T w = T{1};
			cin >> u >> v, u -= offset, v -= offset;
			if constexpr(has_weight) cin >> w;
			directed ? g.orient(u, v, w) : g.link(u, v, w);
		}
		return move(g);
	}
#undef ASSERT
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n, m, from, to;
	long long k;
	cin >> n >> m >> k >> from >> to, -- from, -- to;
	auto g = graph<int>::read(n, m);
	if(k % 2){
		cout << "Yes\n";
		return 0;
	}
	g.set_ignoration_rule([&](int id){
		auto [u, v, _] = g.edge[id];
		return u == from && v == to || u == to && v == from;
	});
	if(n == 2 || g.degree(from) == 0 && g.degree(to) == 0){
		cout << "No\n";
	}
	else if(g.degree(from, false) == 0 && g.degree(to, false) == 0){
		const int inf = numeric_limits<int>::max() / 2;
		int odd_cycle = inf;
		vector<array<int, 2>> dp(n);
		vector<array<int, 2>> q(2 * n);
		for(auto id = 0; id < m; ++ id){
			auto [s, t, _] = g.edge[id];
			ranges::fill(dp, array{-1, -1});
			dp[s][0] = 0;
			q[0] = {s, 0};
			for(auto qbeg = 0, qend = 1; qbeg < qend; ++ qbeg){
				auto [u, par] = q[qbeg];
				for(auto v: g.neighbor(u)){
					if(!~dp[v][!par]){
						dp[v][!par] = dp[u][par] + 1;
						q[qend ++] = {v, !par};
					}
				}
			}
			if(~dp[t][0]){
				ctmin(odd_cycle, 1 + dp[t][0]);
			}
		}
		odd_cycle < inf && k >= 3 + odd_cycle ? cout << "Yes\n" : cout << "No\n";
	}
	else{
		cout << "Yes\n";
	}
	return 0;
}

/*

*/
0