| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 393616 |
2021-04-24T06:11:05 Z |
palilo |
None (KOI18_family) |
C++17 |
|
1 ms |
204 KB |
#include <bits/stdc++.h>
using namespace std;
namespace std {
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template <class Fun>
class y_combinator_result {
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}
template <class... Args>
decltype(auto) operator()(Args&&... args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
}; // namespace std
struct disjoint_set {
vector<int> par;
disjoint_set(int n) : par(n, -1) {}
int find(int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
int get_size(int u) {
return -par[find(u)];
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (par[u] > par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif
int n1, n2, k;
cin >> n1 >> n2 >> k;
int root1 = -1, root2 = -1;
vector<vector<int>> tree1(n1), tree2(n2);
for (int i = 0, p; i < n1; ++i) {
cin >> p, --p;
if (p == -1) root1 = i;
else
tree1[p].emplace_back(i);
}
for (int i = 0, p; i < n2; ++i) {
cin >> p, --p;
if (p == -1) root2 = i;
else
tree2[p].emplace_back(i);
}
assert(~root1);
assert(~root2);
// auto dfs = [&](vector<vector<int>>& tree, int root) {
// vector<int> dp(tree.size());
// fill(dp.begin(), dp.begin() + k, 1);
// vector<int> leaf(tree.size());
// iota(leaf.begin(), leaf.begin() + k, 0);
// y_combinator([&](auto self, int u) -> void {
// for (const auto& v : tree[u]) {
// self(v);
// dp[u] += dp[v];
// leaf[u] = leaf[v];
// }
// })(root);
// return make_pair(dp, leaf);
// };
auto dfs2 = [&](vector<vector<int>>& tree, int root) {
vector<int> dp(tree.size()), leaf(tree.size());
y_combinator([&](auto self, int u) -> int {
if (u < k) {
dp[u] = 1, leaf[u] = u;
return u;
}
dp[u] = 0;
for (const auto& v : tree[u]) {
leaf[u] = self(v);
dp[u] += dp[v];
}
return leaf[u];
})(root);
return make_pair(dp, leaf);
};
const auto [dp1, leaf1] = dfs2(tree1, root1);
const auto [dp2, leaf2] = dfs2(tree2, root2);
assert(dp1[root1] == k);
assert(dp2[root2] == k);
vector<int> vtx((n1 - k) + (n2 - k));
iota(vtx.begin(), vtx.begin() + n1 - k, k);
iota(vtx.begin() + n1 - k, vtx.end(), n1 + k);
sort(vtx.begin(), vtx.end(), [&](auto& a, auto& b) {
return (a < n1 ? dp1[a] : dp2[a - n1]) < (b < n1 ? dp1[b] : dp2[b - n1]);
});
disjoint_set dsu(k);
for (auto u : vtx) {
const auto& tree = u < n1 ? tree1 : tree2;
const auto& dp = u < n1 ? dp1 : dp2;
const auto& leaf = u < n1 ? leaf1 : leaf2;
if (u >= n1) u -= n1;
if (dp[u] == 1) continue;
assert(!tree[u].empty());
for (const auto& v : tree[u])
dsu.merge(leaf[u], leaf[v]);
if (dp[u] != dsu.get_size(leaf[u]))
return cout << "NO", 0;
}
cout << "YES";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
