Test/AtCoder/abc165_f.test.cpp

View this file on GitHub
Last update: 2024-07-07 06:05:03+09:00
Problem: https://atcoder.jp/contests/abc165/tasks/abc165_f

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc165/tasks/abc165_f"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/DataStructure/Undoable/UndoableVector.hpp"

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace zawa;


int main() {
    SetFastIO();
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    for (auto& a : A) std::cin >> a;
    std::vector<std::vector<int>> g(N);
    for (int i{} ; i < N - 1 ; i++) {
        int u, v;
        std::cin >> u >> v;
        u--; v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    const int INF{(int)2e9};
    UndoableVector<int> dp(N, INF);
    std::vector<int> ans(N);
    auto dfs{[&](auto dfs, int v, int p) -> void {
        int pos{(int)std::distance(dp.begin(), std::lower_bound(dp.begin(), dp.end(), A[v]))};
        dp.assign(pos, A[v]);
        ans[v] = (int)std::distance(dp.begin(), std::lower_bound(dp.begin(), dp.end(), INF));
        for (auto x : g[v]) if (x != p) {
            dfs(dfs, x, v);
        }
        dp.undo();
    }};
    dfs(dfs, 0, -1);
    for (int i{} ; i < N ; i++) {
        std::cout << ans[i] << '\n';
    }
}

#line 1 "Test/AtCoder/abc165_f.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc165/tasks/abc165_f"

#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/DataStructure/Undoable/UndoableVector.hpp"

#line 4 "Src/DataStructure/Undoable/UndoableVector.hpp"

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

namespace zawa {

template <class T>
class UndoableVector {
public:
    using Iterator = typename std::vector<T>::const_iterator;

    UndoableVector() = default;

    UndoableVector(usize n) : vec_(n) {}

    UndoableVector(usize n, const T& v) : vec_(n, v) {}

    UndoableVector(const std::vector<T>& vec) : vec_{vec} {}

    UndoableVector(std::vector<T>&& vec) : vec_{std::move(vec)} {}
    
    inline usize size() const {
        return vec_.size();
    }

    Iterator begin() const {
        return vec_.begin();
    }

    Iterator end() const {
        return vec_.end();
    }

    void assign(usize i, const T& v) {
        assert(i < size());
        save(i);
        vec_[i] = v;
    }

    T operator[](usize i) const {
        assert(i < size());
        return vec_[i];
    }

    void undo() {
        assert(history_.size());
        auto [i, v]{history_.back()};
        vec_[i] = v;
        history_.pop_back();
    }

private:
    std::vector<T> vec_; 
    std::vector<std::pair<usize, T>> history_;

    void save(usize i) {
        history_.emplace_back(i, vec_[i]);
    }
};

} // namespace zawa
#line 5 "Test/AtCoder/abc165_f.test.cpp"

#include <algorithm>
#line 8 "Test/AtCoder/abc165_f.test.cpp"
#include <iterator>
#line 10 "Test/AtCoder/abc165_f.test.cpp"
using namespace zawa;


int main() {
    SetFastIO();
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    for (auto& a : A) std::cin >> a;
    std::vector<std::vector<int>> g(N);
    for (int i{} ; i < N - 1 ; i++) {
        int u, v;
        std::cin >> u >> v;
        u--; v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    const int INF{(int)2e9};
    UndoableVector<int> dp(N, INF);
    std::vector<int> ans(N);
    auto dfs{[&](auto dfs, int v, int p) -> void {
        int pos{(int)std::distance(dp.begin(), std::lower_bound(dp.begin(), dp.end(), A[v]))};
        dp.assign(pos, A[v]);
        ans[v] = (int)std::distance(dp.begin(), std::lower_bound(dp.begin(), dp.end(), INF));
        for (auto x : g[v]) if (x != p) {
            dfs(dfs, x, v);
        }
        dp.undo();
    }};
    dfs(dfs, 0, -1);
    for (int i{} ; i < N ; i++) {
        std::cout << ans[i] << '\n';
    }
}