test/aoj/joi/undo_union_find.test.cpp

• View this file on GitHub
• Last update: 2025-05-07 17:51:24+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/0723

Depends on

• Undo可能Union-Find (lib/tree/undo_union_find.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/0723
#include "tree/undo_union_find.hpp"
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

int main(void) {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::pair<int, int>> edges(m);
    for (auto &[x, y] : edges) std::cin >> x >> y, --x, --y;
    std::vector<int> s(n);
    for (int &e : s) std::cin >> e;
    int q;
    std::cin >> q;
    std::vector<std::pair<int, int>> queries(q);
    for (auto &[x, y] : queries) std::cin >> x >> y, --x, --y;

    undo_union_find uf(n);
    std::map<std::pair<int, int>, std::vector<int>> mp;
    for (int i = 0; i < m; ++i) {
        auto [x, y] = edges[i];
        if (s[x] == s[y]) {
            uf.unite(x, y);
        } else {
            if (s[x] > s[y]) std::swap(x, y);
            mp[{s[x], s[y]}].emplace_back(i);
        }
    }

    std::vector<int> ans(q, -1);
    std::map<std::pair<int, int>, std::vector<int>> pm;
    for (int i = 0; i < q; ++i) {
        auto [x, y] = queries[i];
        if (s[x] == s[y]) {
            ans[i] = uf.same(x, y);
        } else {
            if (s[x] > s[y]) std::swap(x, y);
            pm[{s[x], s[y]}].emplace_back(i);
        }
    }

    int snap = uf.snapshot();
    for (auto &[p, v] : pm) {
        for (auto e : mp[p]) uf.unite(edges[e].first, edges[e].second);
        for (auto e : v) ans[e] = uf.same(queries[e].first, queries[e].second);
        uf.rollback(snap);
    }

    for (int i = 0; i < q; ++i) std::cout << ans[i] << '\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: tree/undo_union_find.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	00-sample-01	AC	3 ms	4 MB
g++	00-sample-02	AC	2 ms	3 MB
g++	00-sample-03	AC	2 ms	4 MB
g++	00-sample-04	AC	2 ms	4 MB
g++	01-01	AC	3 ms	4 MB
g++	01-02	AC	3 ms	4 MB
g++	01-03	AC	3 ms	4 MB
g++	01-04	AC	3 ms	4 MB
g++	01-05	AC	3 ms	4 MB
g++	01-06	AC	3 ms	4 MB
g++	01-07	AC	3 ms	4 MB
g++	01-08	AC	3 ms	4 MB
g++	01-09	AC	3 ms	4 MB
g++	01-10	AC	3 ms	4 MB
g++	01-11	AC	3 ms	4 MB
g++	01-12	AC	4 ms	4 MB
g++	01-13	AC	3 ms	4 MB
g++	01-14	AC	3 ms	4 MB
g++	01-15	AC	2 ms	4 MB
g++	01-16	AC	3 ms	4 MB
g++	01-17	AC	3 ms	4 MB
g++	01-18	AC	3 ms	4 MB
g++	01-19	AC	3 ms	4 MB
g++	01-20	AC	3 ms	4 MB
g++	01-21	AC	3 ms	4 MB
g++	01-22	AC	3 ms	4 MB
g++	01-23	AC	2 ms	3 MB
g++	01-24	AC	2 ms	3 MB
g++	03-01	AC	148 ms	22 MB
g++	03-02	AC	140 ms	22 MB
g++	03-03	AC	150 ms	22 MB
g++	03-04	AC	119 ms	15 MB
g++	03-05	AC	143 ms	22 MB
g++	03-06	AC	125 ms	14 MB
g++	03-07	AC	124 ms	14 MB
g++	03-08	AC	134 ms	17 MB
g++	03-09	AC	146 ms	18 MB
g++	03-10	AC	142 ms	20 MB
g++	03-11	AC	79 ms	7 MB
g++	03-12	AC	191 ms	29 MB
g++	03-13	AC	83 ms	11 MB
g++	03-14	AC	164 ms	27 MB
g++	03-15	AC	49 ms	6 MB
g++	03-16	AC	62 ms	6 MB
g++	03-17	AC	105 ms	10 MB
g++	03-18	AC	148 ms	26 MB
g++	03-19	AC	48 ms	5 MB
g++	03-20	AC	65 ms	6 MB
g++	03-21	AC	79 ms	7 MB
g++	03-22	AC	80 ms	7 MB
g++	03-23	AC	42 ms	6 MB
g++	04-01	AC	854 ms	96 MB
g++	04-02	AC	838 ms	96 MB
g++	04-03	AC	1010 ms	97 MB
g++	04-04	AC	781 ms	55 MB
g++	04-05	AC	858 ms	96 MB
g++	04-06	AC	785 ms	59 MB
g++	04-07	AC	781 ms	59 MB
g++	04-08	AC	857 ms	72 MB
g++	04-09	AC	893 ms	79 MB
g++	04-10	AC	881 ms	86 MB
g++	04-11	AC	421 ms	21 MB
g++	04-12	AC	1276 ms	133 MB
g++	04-13	AC	548 ms	44 MB
g++	04-14	AC	1118 ms	129 MB
g++	04-15	AC	218 ms	13 MB
g++	04-16	AC	351 ms	17 MB
g++	04-17	AC	672 ms	35 MB
g++	04-18	AC	907 ms	105 MB
g++	04-19	AC	262 ms	16 MB
g++	04-20	AC	343 ms	16 MB
g++	04-21	AC	389 ms	23 MB
g++	04-22	AC	421 ms	23 MB
g++	04-23	AC	212 ms	16 MB

Back to top page