test/ABC285-D.test.cpp

• View this file on GitHub
• Last update: 2023-02-27 01:26:01+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc285/submissions/39274306

Depends on

• compression (座標圧縮) (src/algorithm/compression.hpp)
• topological_sort (トポロジカルソート) (src/graph/simple/topological_sort.hpp)

Code

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

#include "../src/graph/simple/topological_sort.hpp"
#include "../src/algorithm/compression.hpp"

#include <iostream>
#include <vector>
#include <utility>
#include <string>

int main() {
	// int n; std::cin >> n;
	// std::vector<std::string> buc;
	// std::vector<std::pair<std::string, std::string>> ps(n);
	// for (auto& [s, t] : ps) {
	// 	std::cin >> s >> t;
	// 	buc.push_back(s);
	// 	buc.push_back(t);
	// }
	// zawa::compression comp(buc);
	// std::vector<std::vector<int>> G(comp.size());
	// for (const auto& [s, t] : ps) {
	// 	G[comp[s]].emplace_back(comp[t]);
	// }
	// std::cout << (zawa::topological_sort(G).ok() ? "Yes" : "No") << std::endl;
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 285 - D Change Usernames
 * https://atcoder.jp/contests/abc285/submissions/39274306
 */

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

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

#include <vector>
#include <stack>

namespace zawa {

class topological_sort {
private:
	std::vector<std::vector<int>> G;
	std::vector<int> Ord;
	bool is_dag;

	bool build() {
		std::vector<int> In(G.size(), 0);
		for (std::size_t i = 0 ; i < G.size() ; i++) {
			for (const auto& v : G[i]) {
				In[v]++;
			}
		}
		std::stack<int> S;
		for (std::size_t i = 0 ; i < G.size() ; i++) {
			if (!In[i]) {
				S.push(i);
			}
		}
		while (S.size()) {
			int v = S.top();
			S.pop();
			Ord.push_back(v);
			for (auto x : G[v]) {
				In[x]--;
				if (!In[x]) {
					S.push(x);
				}
			}
		}
		return Ord.size() == G.size();
	}

public:
	topological_sort(const std::vector<std::vector<int>>& _G) : G(_G), is_dag(build()) {}	

	template <class cost_type>
	topological_sort(const std::vector<std::vector<std::pair<int, cost_type>>>& _G) :  G(_G.size()) {
		for (std::size_t i = 0 ; i < _G.size() ; i++) {
			for (auto [v, _] : _G[i]) {
				G[i].push_back(v);
			}
		}	
		is_dag = build();
	}

	inline bool ok() const {
		return is_dag;
	}

	int operator[](int i) {
		return Ord[i];
	}

	inline std::vector<int> get() const {
		return Ord;
	}

	bool unique() const {
		if (!is_dag) {
			return false;
		}
		bool res = true;
		for (std::size_t i = 0 ; i + 1 < G.size() ; i++) {
			bool ok = false;
			for (const auto& v : G[Ord[i]]) {
				ok |= v == Ord[i + 1];
			}
			res &= ok;
		}
		return res;
	}
};

} // namespace zawa
#line 2 "src/algorithm/compression.hpp"

#line 4 "src/algorithm/compression.hpp"
#include <algorithm>

namespace zawa {

template <class T>
class compression {
private:
	std::vector<T> as;
	std::vector<T> uniqued;

public:
	compression(const std::vector<T>& as) : as(as), uniqued(as) {
		std::sort(uniqued.begin(), uniqued.end());
		uniqued.erase(std::unique(uniqued.begin(), uniqued.end()), uniqued.end());
	}

	int operator[](const T& val) {
		return std::lower_bound(uniqued.begin(), uniqued.end(), val) - uniqued.begin();
	}

	int get(std::size_t i) {
		return (*this)[as[i]];
	}

	std::size_t size() {
		return uniqued.size();
	}
};

} // namespace zawa
#line 5 "test/ABC285-D.test.cpp"

#include <iostream>
#line 8 "test/ABC285-D.test.cpp"
#include <utility>
#include <string>

int main() {
	// int n; std::cin >> n;
	// std::vector<std::string> buc;
	// std::vector<std::pair<std::string, std::string>> ps(n);
	// for (auto& [s, t] : ps) {
	// 	std::cin >> s >> t;
	// 	buc.push_back(s);
	// 	buc.push_back(t);
	// }
	// zawa::compression comp(buc);
	// std::vector<std::vector<int>> G(comp.size());
	// for (const auto& [s, t] : ps) {
	// 	G[comp[s]].emplace_back(comp[t]);
	// }
	// std::cout << (zawa::topological_sort(G).ok() ? "Yes" : "No") << std::endl;
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 285 - D Change Usernames
 * https://atcoder.jp/contests/abc285/submissions/39274306
 */

Back to top page