Test/CF/CF316-D.test.cpp

• View this file on GitHub
• Last update: 2024-02-11 01:31:44+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://codeforces.com/contest/570/submission/245736854

Depends on

• Sack (Src/Graph/Tree/Sack.hpp)
• ioまわりの設定 (Src/Template/IOSetting.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

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

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Graph/Tree/Sack.hpp"

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

/*
 * Codeforces Round 316 (Div. 2) - D Tree Requests
 * https://codeforces.com/contest/570/submission/245736854
 */


using namespace zawa;

void solve() {
    SetFastIO();
    int n, q; std::cin >> n >> q;
    Sack sack(n);
    std::vector<int> dep(n);
    for (int i{1} ; i < n ; i++) {
        int p; std::cin >> p;
        sack.addEdge(p - 1, i);
        dep[i] = dep[p - 1] + 1;
    }
    std::string s; std::cin >> s;
    std::vector dat(n, std::vector<std::pair<int, int>>{});
    for (int i{} ; i < q ; i++) {
        int v, h; std::cin >> v >> h;
        v--; h--;
        dat[v].emplace_back(h, i);
    }

    std::vector<bool> ans(q);
    std::vector<std::array<bool, 26>> parity(n);
    for (int i{} ; i < n ; i++) parity[i].fill(false);
    std::vector<int> odd(n);
    auto add{[&](int v) -> void {
        odd[dep[v]] += (parity[dep[v]][s[v] - 'a'] ? -1 : 1);
        parity[dep[v]][s[v] - 'a'] ^= 1;
    }};
    auto del{[&](int v) -> void {
        odd[dep[v]] += (parity[dep[v]][s[v] - 'a'] ? -1 : 1);
        parity[dep[v]][s[v] - 'a'] ^= 1;
    }};
    auto query{[&](int v) -> void {
        for (auto [h, i] : dat[v]) {
            if (h >= n) ans[i] = true;
            else ans[i] = odd[h] <= 1;
        }
    }};
    auto reset{[](){}};
    sack.execute(0, add, del, query, reset);
    for (int i{} ; i < q ; i++) {
        std::cout << (ans[i] ? "Yes" : "No") << '\n';
    }
}

int main() {
#ifdef ONLINE_JUDGE
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}

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

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/Graph/Tree/Sack.hpp"

#line 4 "Src/Graph/Tree/Sack.hpp"

#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

class Sack {
private:    
    static constexpr u32 INVALID{static_cast<u32>(-1)};
    usize n_{};
    std::vector<std::vector<u32>> g_;
    std::vector<u32> sz_, euler_, L_, R_;

    u32 dfsHLD(u32 v, u32 p) {
        sz_[v] = 1;
        usize m{g_[v].size()};
        usize max{};
        if (m > 1u and g_[v][0] == p) std::swap(g_[v][0], g_[v][1]);
        for (u32 i{} ; i < m ; i++) if (g_[v][i] != p) {
            sz_[v] += dfsHLD(g_[v][i], v);
            if (max < sz_[g_[v][i]]) {
                max = sz_[g_[v][i]];
                if (i) std::swap(g_[v][0], g_[v][i]);
            }
        }
        return sz_[v];
    }

    void dfsEuler(u32 v, u32 p, u32& t) {
        euler_[t] = v;
        L_[v] = t++;
        for (auto x : g_[v]) if (x != p) {
            dfsEuler(x, v, t);
        }
        R_[v] = t;
    }

public:
    constexpr usize size() const noexcept {
        return n_;
    }

    Sack() = default;
    Sack(u32 n) 
        : n_{n}, g_(n), sz_(n), euler_(n), L_(n), R_(n) {
        assert(n);
        g_.shrink_to_fit();
        sz_.shrink_to_fit();
        euler_.shrink_to_fit();
        L_.shrink_to_fit();
        R_.shrink_to_fit();
    }
    void addEdge(u32 u, u32 v) {
        assert(u < size());
        assert(v < size());
        g_[u].emplace_back(v);
        g_[v].emplace_back(u);
    }

    const std::vector<u32>& operator[](u32 v) const noexcept {
        assert(v < size());
        return g_[v];
    }

    template <class ADD, class DEL, class QUERY, class RESET>
    u32 execute(u32 root, const ADD& add, const DEL& del, const QUERY& query, const RESET& reset) {
        dfsHLD(root, INVALID);
        u32 t{};
        dfsEuler(root, INVALID, t);
        
        auto sack{[&](auto dfs, u32 v, u32 p, bool keep) -> void {
            usize m{g_[v].size()};
            for (u32 i{1} ; i < m ; i++) if (g_[v][i] != p) {
                dfs(dfs, g_[v][i], v, false);
            }
            if (sz_[v] > 1u) dfs(dfs, g_[v][0], v, true);
            if (sz_[v] > 1u) {
                for (u32 i{R_[g_[v][0]]} ; i < R_[v] ; i++) {
                    add(euler_[i]);
                }
            }
            add(v);
            query(v);
            if (!keep) {
                for (u32 i{L_[v]} ; i < R_[v] ; i++) {
                    del(euler_[i]);
                }
                reset();
            }
        }};
        sack(sack, root, INVALID, false);

        return sz_[root];
    }
};

} // namespace zawa
#line 5 "Test/CF/CF316-D.test.cpp"

#line 9 "Test/CF/CF316-D.test.cpp"

/*
 * Codeforces Round 316 (Div. 2) - D Tree Requests
 * https://codeforces.com/contest/570/submission/245736854
 */


using namespace zawa;

void solve() {
    SetFastIO();
    int n, q; std::cin >> n >> q;
    Sack sack(n);
    std::vector<int> dep(n);
    for (int i{1} ; i < n ; i++) {
        int p; std::cin >> p;
        sack.addEdge(p - 1, i);
        dep[i] = dep[p - 1] + 1;
    }
    std::string s; std::cin >> s;
    std::vector dat(n, std::vector<std::pair<int, int>>{});
    for (int i{} ; i < q ; i++) {
        int v, h; std::cin >> v >> h;
        v--; h--;
        dat[v].emplace_back(h, i);
    }

    std::vector<bool> ans(q);
    std::vector<std::array<bool, 26>> parity(n);
    for (int i{} ; i < n ; i++) parity[i].fill(false);
    std::vector<int> odd(n);
    auto add{[&](int v) -> void {
        odd[dep[v]] += (parity[dep[v]][s[v] - 'a'] ? -1 : 1);
        parity[dep[v]][s[v] - 'a'] ^= 1;
    }};
    auto del{[&](int v) -> void {
        odd[dep[v]] += (parity[dep[v]][s[v] - 'a'] ? -1 : 1);
        parity[dep[v]][s[v] - 'a'] ^= 1;
    }};
    auto query{[&](int v) -> void {
        for (auto [h, i] : dat[v]) {
            if (h >= n) ans[i] = true;
            else ans[i] = odd[h] <= 1;
        }
    }};
    auto reset{[](){}};
    sack.execute(0, add, del, query, reset);
    for (int i{} ; i < q ; i++) {
        std::cout << (ans[i] ? "Yes" : "No") << '\n';
    }
}

int main() {
#ifdef ONLINE_JUDGE
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}

Back to top page