test/aoj/challenge/2270.test.cpp

• View this file on GitHub
• Last update: 2026-03-24 01:55:57+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2270

Depends on

• めぐる式二分探索 (lib/algorithm/binary_search.hpp)
• 座標圧縮 (lib/algorithm/compress.hpp)
• 線形 Sparse Table (lib/data_structure/linear_sparse_table.hpp)
• スパーステーブル (lib/data_structure/sparse_table.hpp)
• 重み付きウェーブレット行列 (lib/data_structure/wavelet_matrix_rectangle_sum.hpp)
• 重み付きグラフ (lib/graph/graph.hpp)
• 完備辞書 (lib/internal/internal_bit_vector.hpp)
• lib/internal/internal_csr.hpp
• lib/tree/linear_lca.hpp

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2270
#include <iostream>
#include <vector>
#include "algorithm/binary_search.hpp"
#include "algorithm/compress.hpp"
#include "data_structure/wavelet_matrix_rectangle_sum.hpp"
#include "graph/graph.hpp"
#include "tree/linear_lca.hpp"

int main(void) {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (auto &e : a) std::cin >> e;
    Graph<void> g(n);
    g.input_edges(n - 1);
    coordinate_compression cps(a);
    a = cps.compress(a);
    std::vector<int> in(n), val(n * 2), w(n * 2);
    int c = 0;
    auto dfs = [&](auto self, int x, int p) -> void {
        in[x] = c;
        w[c] = 1;
        val[c++] = a[x];
        for (auto e : g[x]) {
            if (e.to() == p) continue;
            self(self, e.to(), x);
        }
        w[c] = -1;
        val[c++] = a[x];
    };
    dfs(dfs, 0, -1);
    linear_lca lca(g);
    wavelet_matrix_rectangle_sum<int, int, 18> wm(val, w);
    while (q--) {
        int u, v, k;
        std::cin >> u >> v >> k;
        --u, --v;
        auto f = [&](int y) {
            return wm.rect_sum(0, in[u] + 1, y) + wm.rect_sum(0, in[v] + 1, y) -
                       wm.rect_sum(0, in[lca(u, v)] + 1, y) - wm.rect_sum(0, in[lca(u, v)], y) <
                   k;
        };
        auto ans = meguru_binary_search(0, cps.size() + 1, f);
        std::cout << cps[ans] << '\n';
    }

    return 0;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: algorithm/binary_search.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	testcase_00	AC	3 ms	4 MB
g++	testcase_01	AC	2 ms	3 MB
g++	testcase_02	AC	2 ms	3 MB
g++	testcase_03	AC	3 ms	4 MB
g++	testcase_04	AC	3 ms	4 MB
g++	testcase_05	AC	3 ms	4 MB
g++	testcase_06	AC	3 ms	4 MB
g++	testcase_07	AC	3 ms	4 MB
g++	testcase_08	AC	3 ms	3 MB
g++	testcase_09	AC	3 ms	4 MB
g++	testcase_10	AC	3 ms	3 MB
g++	testcase_11	AC	12 ms	4 MB
g++	testcase_12	AC	11 ms	4 MB
g++	testcase_13	AC	12 ms	4 MB
g++	testcase_14	AC	9 ms	4 MB
g++	testcase_15	AC	9 ms	4 MB
g++	testcase_16	AC	9 ms	4 MB
g++	testcase_17	AC	9 ms	4 MB
g++	testcase_18	AC	9 ms	4 MB
g++	testcase_19	AC	1390 ms	33 MB
g++	testcase_20	AC	1411 ms	33 MB
g++	testcase_21	AC	1527 ms	33 MB
g++	testcase_22	AC	1491 ms	36 MB
g++	testcase_23	AC	1301 ms	34 MB
g++	testcase_24	AC	1393 ms	34 MB
g++	testcase_25	AC	1443 ms	35 MB
g++	testcase_26	AC	1433 ms	37 MB
g++	testcase_27	AC	1304 ms	37 MB
g++	testcase_28	AC	1347 ms	36 MB
g++	testcase_29	AC	1316 ms	35 MB
g++	testcase_30	AC	1376 ms	33 MB

Back to top page