test/ABC289-D.test.cpp

• View this file on GitHub
• Last update: 2023-02-13 09:43:35+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc289/submissions/38854333

Depends on

• reachability (到達可能性) (src/graph/simple/reachability.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../src/graph/simple/reachability.hpp"

#include <iostream>
#include <vector>
#include <set>

int main() {
	// int N; std::cin >> N;
	// std::vector A(N, 0);
	// for (auto& a : A) {
	// 	std::cin >> a;
	// }
	// int M; std::cin >> M;
	// std::set<int> B;
	// for (int _ = 0 ; _ < M ; _++) {
	// 	int b; std::cin >> b;
	// 	B.insert(b);
	// }
	// int X; std::cin >> X;
	// std::vector G(X + 1, std::vector(0, 0));
	// for (int i = 0 ; i < X + 1 ; i++) {
	// 	if (!B.count(i)) {
	// 		for (const auto& a : A) {
	// 			if (i + a < X + 1) {
	// 				G[i].push_back(i + a);
	// 			}
	// 		}
	// 	}
	// }
	// std::cout << (zawa::reachability(G, 0, X) ? "Yes" : "No") << std::endl;
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 289-D Step Up Robot
 * https://atcoder.jp/contests/abc289/submissions/38854333
 */

#line 1 "test/ABC289-D.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "src/graph/simple/reachability.hpp"

#include <vector>
#include <stack>
#include <utility>

namespace zawa {

bool reachability(const std::vector<std::vector<int>>& G, int from, int to) {
	std::stack<int> stk;
	std::vector visited(G.size(), false);
	visited[from] = true;
	stk.emplace(from);
	while (stk.size()) {
		int v = stk.top();
		stk.pop();
		if (v == to) {
			return true;
		}
		for (const auto& x : G[v]) {
			if (!visited[x]) {
				visited[x] = true;
				stk.emplace(x);
			}
		}
	}
	return false;
}

template <class cost_type>
bool reachability(const std::vector<std::vector<std::pair<int, cost_type>>>& G, int from, int to) {
	std::vector tmp(G.size(), std::vector(0, 0));
	for (int i = 0 ; i < (int)G.size() ; i++) {
		for (auto [x, _] : G[i]) {
			tmp[i].emplace(x);
		}
	}
	return reachability(tmp, from, to);
}

} // namespace zawa
#line 4 "test/ABC289-D.test.cpp"

#include <iostream>
#line 7 "test/ABC289-D.test.cpp"
#include <set>

int main() {
	// int N; std::cin >> N;
	// std::vector A(N, 0);
	// for (auto& a : A) {
	// 	std::cin >> a;
	// }
	// int M; std::cin >> M;
	// std::set<int> B;
	// for (int _ = 0 ; _ < M ; _++) {
	// 	int b; std::cin >> b;
	// 	B.insert(b);
	// }
	// int X; std::cin >> X;
	// std::vector G(X + 1, std::vector(0, 0));
	// for (int i = 0 ; i < X + 1 ; i++) {
	// 	if (!B.count(i)) {
	// 		for (const auto& a : A) {
	// 			if (i + a < X + 1) {
	// 				G[i].push_back(i + a);
	// 			}
	// 		}
	// 	}
	// }
	// std::cout << (zawa::reachability(G, 0, X) ? "Yes" : "No") << std::endl;
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 289-D Step Up Robot
 * https://atcoder.jp/contests/abc289/submissions/38854333
 */

Back to top page