test/aoj/2955/main.test.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2955"
#include <iostream>
#include <map>
#include <vector>
#include "Mylib/DataStructure/UnionFind/unionfind.cpp"
#include "Mylib/IO/input_vector.cpp"
#include "Mylib/Typical/subset_sum_limited.cpp"
namespace hl = haar_lib;
int main() {
int N, R;
std::cin >> N >> R;
auto p = hl::input_vector<int>(N);
for (auto &x : p) x -= 1;
hl::unionfind uf(N);
for (int i = 0; i < N; ++i) {
uf.merge(i, p[i]);
}
std::map<int, int> cycles;
for (int i = 0; i < N; ++i) {
if (i == uf.root_of(i)) cycles[uf.size_of(i)] += 1;
}
std::vector<int> a, m;
for (auto &[k, v] : cycles) {
a.push_back(k);
m.push_back(v);
}
bool ans = hl::subset_sum_limited(a.size(), R, a, m)[R];
std::cout << (ans ? "Yes" : "No") << std::endl;
return 0;
}
#line 1 "test/aoj/2955/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2955"
#include <iostream>
#include <map>
#include <vector>
#line 2 "Mylib/DataStructure/UnionFind/unionfind.cpp"
#include <algorithm>
#include <numeric>
#line 5 "Mylib/DataStructure/UnionFind/unionfind.cpp"
namespace haar_lib {
class unionfind {
int n_, count_;
mutable std::vector<int> parent_;
std::vector<int> depth_, size_;
public:
unionfind() {}
unionfind(int n) : n_(n), count_(n), parent_(n), depth_(n, 1), size_(n, 1) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int root_of(int i) const {
if (parent_[i] == i)
return i;
else
return parent_[i] = root_of(parent_[i]);
}
bool is_same(int i, int j) const { return root_of(i) == root_of(j); }
int merge(int i, int j) {
const int ri = root_of(i), rj = root_of(j);
if (ri == rj)
return ri;
else {
--count_;
if (depth_[ri] < depth_[rj]) {
parent_[ri] = rj;
size_[rj] += size_[ri];
return rj;
} else {
parent_[rj] = ri;
size_[ri] += size_[rj];
if (depth_[ri] == depth_[rj]) ++depth_[ri];
return ri;
}
}
}
int size_of(int i) const { return size_[root_of(i)]; }
int count_groups() const { return count_; }
auto get_groups() const {
std::vector<std::vector<int>> ret(n_);
for (int i = 0; i < n_; ++i) {
ret[root_of(i)].push_back(i);
}
ret.erase(
std::remove_if(
ret.begin(), ret.end(),
[](const auto &a) { return a.empty(); }),
ret.end());
return ret;
}
};
} // namespace haar_lib
#line 4 "Mylib/IO/input_vector.cpp"
namespace haar_lib {
template <typename T>
std::vector<T> input_vector(int N) {
std::vector<T> ret(N);
for (int i = 0; i < N; ++i) std::cin >> ret[i];
return ret;
}
template <typename T>
std::vector<std::vector<T>> input_vector(int N, int M) {
std::vector<std::vector<T>> ret(N);
for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
return ret;
}
} // namespace haar_lib
#line 2 "Mylib/Typical/subset_sum_limited.cpp"
#include <cassert>
#line 4 "Mylib/Typical/subset_sum_limited.cpp"
namespace haar_lib {
auto subset_sum_limited(int N, int K, const std::vector<int> &a, const std::vector<int> &m) {
assert((int) a.size() == N and (int) m.size() == N);
std::vector<int> dp(K + 1, -1);
dp[0] = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= K; ++j) {
if (dp[j] >= 0) {
dp[j] = m[i];
} else if (j < a[i] or dp[j - a[i]] <= 0) {
dp[j] = -1;
} else {
dp[j] = dp[j - a[i]] - 1;
}
}
}
for (int i = 0; i <= K; ++i) dp[i] = dp[i] >= 0;
return dp;
}
} // namespace haar_lib
#line 9 "test/aoj/2955/main.test.cpp"
namespace hl = haar_lib;
int main() {
int N, R;
std::cin >> N >> R;
auto p = hl::input_vector<int>(N);
for (auto &x : p) x -= 1;
hl::unionfind uf(N);
for (int i = 0; i < N; ++i) {
uf.merge(i, p[i]);
}
std::map<int, int> cycles;
for (int i = 0; i < N; ++i) {
if (i == uf.root_of(i)) cycles[uf.size_of(i)] += 1;
}
std::vector<int> a, m;
for (auto &[k, v] : cycles) {
a.push_back(k);
m.push_back(v);
}
bool ans = hl::subset_sum_limited(a.size(), R, a, m)[R];
std::cout << (ans ? "Yes" : "No") << std::endl;
return 0;
}
Back to top page