Submission #423385


Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

class UF
{
private:
    int m_size;
    int m_query_num;
    vector<int> m_data;

public:
    UF(int s, int q) : m_size(s), m_query_num(q) {}
    void init();
    void unit(const int a, const int b);
    int find(const int a);
    void checkSame(const int a, const int b);
};


void UF::init(){
    m_data.resize(m_size);

    for (int i = 0; i < m_size; ++i) {
        m_data.at(i) = i;
    }
}


// rootを探す
int UF::find(const int a) {
    if (m_data.at(a) == a) return m_data.at(a);

    return (m_data.at(a) = this->find(m_data.at(a)));
}


void UF::unit(const int a, const int b) {
    int root_a = find(a);
    int root_b = find(b);

    if (root_a == root_b) return;

    m_data.at(root_a) = root_b;
}



void UF::checkSame(const int a, const int b) {
    int root_a = this->find(m_data.at(a));
    int root_b = this->find(m_data.at(b));

    if (root_a == root_b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


int main()
{
    int n, q;

    cin >> n >> q;

    UF uf(n, q);
    uf.init();

    for (int i = 0; i < q; ++i) {
        int q, a, b;
        cin >> q >> a >> b;
        
        switch (q) {
            case 0:
                uf.unit(a, b);
                break;
            case 1:
                uf.checkSame(a, b);
                break;
            default:
                break;
        }
    }
    return 0;
}

Submission Info

Submission Time
Task B - Union Find
User ryoyuki
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1534 Byte
Status AC
Exec Time 976 ms
Memory 1312 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 19
Set Name Test Cases
Sample 00_sample_01.txt
All 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 25 ms 924 KB
subtask_01_01.txt AC 552 ms 924 KB
subtask_01_02.txt AC 23 ms 1192 KB
subtask_01_03.txt AC 627 ms 676 KB
subtask_01_04.txt AC 976 ms 1116 KB
subtask_01_05.txt AC 65 ms 920 KB
subtask_01_06.txt AC 68 ms 1184 KB
subtask_01_07.txt AC 703 ms 796 KB
subtask_01_08.txt AC 967 ms 1120 KB
subtask_01_09.txt AC 27 ms 804 KB
subtask_01_10.txt AC 24 ms 1312 KB
subtask_01_11.txt AC 873 ms 804 KB
subtask_01_12.txt AC 934 ms 1188 KB
subtask_01_13.txt AC 708 ms 800 KB
subtask_01_14.txt AC 30 ms 1188 KB
subtask_01_15.txt AC 813 ms 920 KB
subtask_01_16.txt AC 877 ms 1188 KB
subtask_01_17.txt AC 678 ms 1192 KB
subtask_01_18.txt AC 672 ms 1132 KB