test/DSL_1_B.test.cpp

• View this file on GitHub
• Last update: 2025-05-28 17:58:43+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B

Depends on

• Union Find With Potential (data_structure/unionfind_with_potential.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B"

#include <sys/types.h>  // for uint

#include <data_structure/unionfind_with_potential.hpp>  // for weighted_unionfind
#include <fastio/base.hpp>                              // for FASTIO, cin, cout
#include <fastio/char/write.hpp>                        // for operator<<
#include <fastio/signed/read.hpp>                       // for operator>>
#include <fastio/signed/write.hpp>                      // for operator<<
#include <fastio/unsigned/read.hpp>                     // for operator>>
#include <templates/macro/abbrev/endl.hpp>              // for endl
#include <templates/rep.hpp>                            // for rep
#include <templates/template.hpp>
#include <version>  // for std

int main() {
    int n, q;
    cin >> n >> q;
    UnionFindWithPotential uf(n);
    rep(_, q) {
        uint T;
        cin >> T;
        if (T) {
            int x, y;
            cin >> x >> y;
            if (!uf.same(x, y)) {
                cout << '?' << endl;
            } else {
                cout << uf.weight(x, y) << endl;
            }
        } else {
            int x, y, z;
            cin >> x >> y >> z;
            uf.merge(x, y, z);
        }
    }
}

#line 1 "test/DSL_1_B.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B"

#include <sys/types.h>  // for uint

#include <data_structure/unionfind_with_potential.hpp>  // for weighted_unionfind
#include <fastio/base.hpp>                              // for FASTIO, cin, cout
#include <fastio/char/write.hpp>                        // for operator<<
#include <fastio/signed/read.hpp>                       // for operator>>
#include <fastio/signed/write.hpp>                      // for operator<<
#include <fastio/unsigned/read.hpp>                     // for operator>>
#include <templates/macro/abbrev/endl.hpp>              // for endl
#include <templates/rep.hpp>                            // for rep
#include <templates/template.hpp>
#include <version>  // for std

int main() {
    int n, q;
    cin >> n >> q;
    UnionFindWithPotential uf(n);
    rep(_, q) {
        uint T;
        cin >> T;
        if (T) {
            int x, y;
            cin >> x >> y;
            if (!uf.same(x, y)) {
                cout << '?' << endl;
            } else {
                cout << uf.weight(x, y) << endl;
            }
        } else {
            int x, y, z;
            cin >> x >> y >> z;
            uf.merge(x, y, z);
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	82 ms	4 MB
g++	01_small_00.in	AC	4 ms	4 MB
g++	02_corner_00.in	AC	4 ms	4 MB
g++	03_general_00.in	AC	4 ms	4 MB
g++	04_rand_00.in	AC	4 ms	4 MB
g++	04_rand_01.in	AC	4 ms	4 MB
g++	04_rand_02.in	AC	4 ms	4 MB
g++	04_rand_03.in	AC	4 ms	4 MB
g++	04_rand_04.in	AC	4 ms	4 MB
g++	04_rand_05.in	AC	4 ms	4 MB
g++	04_rand_06.in	AC	4 ms	4 MB
g++	04_rand_07.in	AC	4 ms	4 MB
g++	05_large_00.in	AC	6 ms	5 MB
g++	05_large_01.in	AC	8 ms	5 MB
g++	06_maximum_00.in	AC	11 ms	6 MB
g++	06_maximum_02.in	AC	11 ms	6 MB
g++	07_dense_00.in	AC	5 ms	4 MB
g++	07_dense_01.in	AC	6 ms	4 MB
g++	07_dense_02.in	AC	9 ms	5 MB
g++	07_dense_03.in	AC	13 ms	6 MB
g++	08_shell_00.in	AC	17 ms	10 MB
g++	09_extreme_line_00.in	AC	17 ms	10 MB
g++	09_extreme_same_00.in	AC	20 ms	10 MB
g++	09_extreme_same_01.in	AC	21 ms	10 MB

Back to top page