結果
| 問題 |
No.3291 K-step Navigation
|
| ユーザー |
 Aeren
|
| 提出日時 | 2025-10-03 22:09:14 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,010 bytes |
| コンパイル時間 | 2,725 ms |
| コンパイル使用メモリ | 286,088 KB |
| 実行使用メモリ | 7,720 KB |
| 最終ジャッジ日時 | 2025-10-03 22:09:19 |
| 合計ジャッジ時間 | 4,390 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 42 WA * 8 |
ソースコード
// #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(n == 2 || g.degree(from) == 0 && g.degree(to) == 0){
k % 2 ? cout << "Yes\n" : cout << "No\n";
}
else{
cout << "Yes\n";
}
return 0;
}
/*
*/