test/DataStructure/union_find_with_monoid/aoj-2664.cpp

• View this file on GitHub
• Last update: 2025-08-25 23:31:57+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2664

Depends on

• モノイド付きUnion Find (DataStructure/union_find_with_monoid.hpp)

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2664

#include "DataStructure/union_find_with_monoid.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N;
    cin >> N;

    unordered_map<string, int> mp;
    vector<int> x(N);
    for (int i = 0; i < N; i++)
    {
        string a;
        cin >> a >> x[i];
        mp[a] = mp.size();
    }

    int M;
    cin >> M;

    auto op = [&](int from, int to)
    {
        x[to] = min(x[from], x[to]);
    };

    UnionFindWithMonoid uf(N);
    for (int i = 0; i < M; i++)
    {
        string s, t;
        cin >> s >> t;
        uf.merge(mp[s], mp[t], op);
    }

    int ans = 0;
    for (auto group : uf.groups())
    {
        ans += group.size() * x[uf.leader(group.front())];
    }
    cout << ans << endl;

    return 0;
}

#line 1 "test/DataStructure/union_find_with_monoid/aoj-2664.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2664

#line 1 "DataStructure/union_find_with_monoid.hpp"
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;

class UnionFindWithMonoid : public atcoder::dsu
{
public:
    UnionFindWithMonoid(int N) : atcoder::dsu(N) {}

    int merge(int u, int v, function<void(int, int)> op)
    {
        if (this->same(u, v))
        {
            return this->leader(u);
        }

        u = this->leader(u), v = this->leader(v);

        int to = atcoder::dsu::merge(u, v);
        int from = u ^ v ^ to;
        op(from, to);

        return to;
    }
};
#line 5 "test/DataStructure/union_find_with_monoid/aoj-2664.cpp"

using namespace std;

int main()
{
    int N;
    cin >> N;

    unordered_map<string, int> mp;
    vector<int> x(N);
    for (int i = 0; i < N; i++)
    {
        string a;
        cin >> a >> x[i];
        mp[a] = mp.size();
    }

    int M;
    cin >> M;

    auto op = [&](int from, int to)
    {
        x[to] = min(x[from], x[to]);
    };

    UnionFindWithMonoid uf(N);
    for (int i = 0; i < M; i++)
    {
        string s, t;
        cin >> s >> t;
        uf.merge(mp[s], mp[t], op);
    }

    int ans = 0;
    for (auto group : uf.groups())
    {
        ans += group.size() * x[uf.leader(group.front())];
    }
    cout << ans << endl;

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	4 ms	3 MB
g++	00_sample_01.in	AC	4 ms	3 MB
g++	01_challenge_00.in	AC	4 ms	3 MB
g++	01_challenge_01.in	AC	4 ms	3 MB
g++	10_random_small_00.in	AC	4 ms	3 MB
g++	10_random_small_01.in	AC	4 ms	3 MB
g++	10_random_small_02.in	AC	4 ms	3 MB
g++	10_random_small_03.in	AC	4 ms	3 MB
g++	10_random_small_04.in	AC	4 ms	3 MB
g++	10_random_small_05.in	AC	4 ms	3 MB
g++	10_random_small_06.in	AC	4 ms	3 MB
g++	10_random_small_07.in	AC	4 ms	3 MB
g++	10_random_small_08.in	AC	4 ms	3 MB
g++	10_random_small_09.in	AC	4 ms	3 MB
g++	10_random_small_10.in	AC	4 ms	3 MB
g++	10_random_small_11.in	AC	4 ms	3 MB
g++	10_random_small_12.in	AC	4 ms	3 MB
g++	10_random_small_13.in	AC	4 ms	3 MB
g++	10_random_small_14.in	AC	4 ms	3 MB
g++	10_random_small_15.in	AC	4 ms	3 MB
g++	10_random_small_16.in	AC	4 ms	3 MB
g++	10_random_small_17.in	AC	4 ms	3 MB
g++	10_random_small_18.in	AC	4 ms	3 MB
g++	10_random_small_19.in	AC	4 ms	3 MB
g++	10_random_small_20.in	AC	4 ms	3 MB
g++	10_random_small_21.in	AC	4 ms	3 MB
g++	10_random_small_22.in	AC	4 ms	3 MB
g++	10_random_small_23.in	AC	4 ms	3 MB
g++	10_random_small_24.in	AC	4 ms	3 MB
g++	10_random_small_25.in	AC	4 ms	3 MB
g++	10_random_small_26.in	AC	4 ms	3 MB
g++	10_random_small_27.in	AC	4 ms	3 MB
g++	10_random_small_28.in	AC	4 ms	3 MB
g++	10_random_small_29.in	AC	4 ms	3 MB
g++	10_random_small_30.in	AC	4 ms	3 MB
g++	10_random_small_31.in	AC	4 ms	3 MB
g++	10_random_small_32.in	AC	4 ms	3 MB
g++	10_random_small_33.in	AC	4 ms	3 MB
g++	10_random_small_34.in	AC	4 ms	3 MB
g++	10_random_small_35.in	AC	4 ms	3 MB
g++	10_random_small_36.in	AC	4 ms	3 MB
g++	10_random_small_37.in	AC	4 ms	3 MB
g++	10_random_small_38.in	AC	4 ms	3 MB
g++	10_random_small_39.in	AC	4 ms	3 MB
g++	11_random_large_00.in	AC	6 ms	4 MB
g++	11_random_large_01.in	AC	5 ms	4 MB
g++	11_random_large_02.in	AC	6 ms	4 MB
g++	11_random_large_03.in	AC	6 ms	4 MB
g++	11_random_large_04.in	AC	4 ms	4 MB
g++	11_random_large_05.in	AC	6 ms	4 MB
g++	11_random_large_06.in	AC	5 ms	4 MB
g++	11_random_large_07.in	AC	6 ms	4 MB
g++	11_random_large_08.in	AC	5 ms	4 MB
g++	11_random_large_09.in	AC	5 ms	4 MB
g++	12_random_maximum_00.in	AC	7 ms	4 MB
g++	12_random_maximum_01.in	AC	7 ms	4 MB
g++	12_random_maximum_02.in	AC	7 ms	4 MB
g++	12_random_maximum_03.in	AC	7 ms	4 MB
g++	12_random_maximum_04.in	AC	7 ms	4 MB
g++	12_random_maximum_05.in	AC	6 ms	4 MB
g++	12_random_maximum_06.in	AC	7 ms	4 MB
g++	12_random_maximum_07.in	AC	7 ms	4 MB
g++	12_random_maximum_08.in	AC	7 ms	4 MB
g++	12_random_maximum_09.in	AC	6 ms	4 MB
g++	13_random_Meq0_00.in	AC	6 ms	4 MB

Back to top page