Submission #8794052


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

class UnionFind {
public:
    vector<int> data;
 	UnionFind(int size) : data(size, -1) { }
 	bool connect(int x, int y) {
  		x = root(x); y = root(y);
  		if (x != y) {
   			if (data[y] < data[x]) swap(x, y);
        data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

void solve(long long N, long long M, std::vector<long long> a, std::vector<long long> b, long long Q, std::vector<long long> x, std::vector<long long> y){
    vector<pair<pair<ll, ll>, int>> Querys;
    for(int i = 0;i < Q;i++){
        Querys.push_back(make_pair(make_pair(x[i], y[i]), i));
    }
    vector<int> ans(Q);
    UnionFind check(N + 1);
    for(int i = 0;i < M;i++)check.connect(a[i], b[i]);
    queue<pair<pair<int, int>, vector<pair<pair<ll, ll>, int>>>> range;
    range.push(make_pair(make_pair(0, M), vector<pair<pair<ll, ll>, int>>()));
    for(int i = 0;i < Q;i++){
        auto p = Querys[i];
        if(check.same(p.first.first, p.first.second))range.front().second.push_back(p);
        else ans[i] = -1;
    }
    while (!range.empty())
    {
        if(range.front().second.size() == 0){
            range.pop();
            continue;
        }
        UnionFind Uni(N + 1);
        queue<pair<pair<int, int>, vector<pair<pair<ll, ll>, int>>>> next_range;
        for(int k = 0;k < M;k++){
            while(!range.empty()){
                if(k == (range.front().first.first + range.front().first.second) / 2){
                    pair<pair<int, int>, vector<pair<pair<ll, ll>, int>>> usi = range.front();
                    range.pop();
                    vector<pair<pair<ll, ll>, int>> ok;
                    vector<pair<pair<ll, ll>, int>> ng;
                    for(auto q : usi.second){
                        if(Uni.same(q.first.first, q.first.second)){
                            ok.push_back(q);
                        }else{
                            ng.push_back(q);
                        }
                    }
                    if(ok.size() != 0)next_range.push(make_pair(make_pair(usi.first.first, (usi.first.first + usi.first.second)/2), ok));
                    if(ng.size() != 0)next_range.push(make_pair(make_pair((usi.first.first + usi.first.second)/2, usi.first.second), ng));
                }else{
                    break;
                }
            }
            Uni.connect(a[k], b[k]);
        }
        while(!next_range.empty()){
            auto q = next_range.front();
            next_range.pop();
            if(q.first.second - q.first.first <= 1){
                for(auto qq : q.second){
                    ans[qq.second] = q.first.second;
                }
            }else{
                range.push(q);
            }
        }
    }
    for(int i = 0;i < ans.size();i++){
        cout<<ans[i]<<endl;
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> a(M);
    std::vector<long long> b(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&a[i]);
        scanf("%lld",&b[i]);
    }
    long long Q;
    scanf("%lld",&Q);
    std::vector<long long> x(Q);
    std::vector<long long> y(Q);
    for(int i = 0 ; i < Q ; i++){
        scanf("%lld",&x[i]);
        scanf("%lld",&y[i]);
    }
    solve(N, M, std::move(a), std::move(b), Q, std::move(x), std::move(y));
    return 0;
}

Submission Info

Submission Time
Task H - Union Sets
User hamuhei4869
Language C++14 (GCC 5.4.1)
Score 600
Code Size 3907 Byte
Status AC
Exec Time 313 ms
Memory 19132 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:94:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&N);
                     ^
./Main.cpp:96:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&M);
                     ^
./Main.cpp:100:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i]);
                            ^
./Main.cpp:101:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&b[i]);
                            ^
./Main.cpp:104:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&Q);
                     ^
...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 49
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_1.txt AC 1 ms 256 KB
subtask_1_10.txt AC 18 ms 1280 KB
subtask_1_11.txt AC 154 ms 10124 KB
subtask_1_12.txt AC 3 ms 512 KB
subtask_1_13.txt AC 3 ms 384 KB
subtask_1_14.txt AC 2 ms 256 KB
subtask_1_15.txt AC 58 ms 3968 KB
subtask_1_16.txt AC 5 ms 512 KB
subtask_1_17.txt AC 17 ms 1376 KB
subtask_1_18.txt AC 2 ms 256 KB
subtask_1_19.txt AC 3 ms 512 KB
subtask_1_2.txt AC 1 ms 256 KB
subtask_1_20.txt AC 1 ms 256 KB
subtask_1_21.txt AC 10 ms 912 KB
subtask_1_22.txt AC 1 ms 384 KB
subtask_1_23.txt AC 175 ms 5232 KB
subtask_1_24.txt AC 175 ms 5232 KB
subtask_1_25.txt AC 175 ms 5232 KB
subtask_1_26.txt AC 178 ms 5744 KB
subtask_1_27.txt AC 307 ms 17652 KB
subtask_1_28.txt AC 313 ms 17788 KB
subtask_1_29.txt AC 178 ms 6260 KB
subtask_1_3.txt AC 1 ms 256 KB
subtask_1_30.txt AC 175 ms 5748 KB
subtask_1_31.txt AC 177 ms 5232 KB
subtask_1_32.txt AC 177 ms 5748 KB
subtask_1_33.txt AC 297 ms 17828 KB
subtask_1_34.txt AC 311 ms 19132 KB
subtask_1_35.txt AC 177 ms 6260 KB
subtask_1_36.txt AC 171 ms 6004 KB
subtask_1_37.txt AC 173 ms 5620 KB
subtask_1_38.txt AC 177 ms 5872 KB
subtask_1_39.txt AC 306 ms 16840 KB
subtask_1_4.txt AC 4 ms 640 KB
subtask_1_40.txt AC 300 ms 17116 KB
subtask_1_41.txt AC 179 ms 13256 KB
subtask_1_42.txt AC 190 ms 15648 KB
subtask_1_43.txt AC 264 ms 18528 KB
subtask_1_44.txt AC 298 ms 18512 KB
subtask_1_45.txt AC 173 ms 5620 KB
subtask_1_46.txt AC 176 ms 5232 KB
subtask_1_5.txt AC 24 ms 1500 KB
subtask_1_6.txt AC 3 ms 512 KB
subtask_1_7.txt AC 1 ms 256 KB
subtask_1_8.txt AC 1 ms 256 KB
subtask_1_9.txt AC 31 ms 1404 KB