Submission #19560048


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#include<atcoder/dsu>
using namespace atcoder;
using ll = long long;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a) (a).begin(),(a).end()
void Main(){
    int n, m, q;
    cin >> n >> m;
    vector<int> a(m), b(m);
    For(i,0,m) cin >> a[i] >> b[i];
    cin >> q;
    vector<int> x(q), y(q), ng(q, 0), ok(q, m);
    vector<vector<int>> mid(m+1);
    For(i,0,q) cin >> x[i] >> y[i];
    For(i,0,q) mid[m/2].emplace_back(i);
    For(_,0,20){
        dsu uf(n+1);
        For(i,0,m){
            uf.merge(a[i], b[i]);
            for(auto query:mid[i]){
                if(uf.same(x[query], y[query])){
                    ok[query] = i;
                }
                else{
                    ng[query] = i;
                }
                mid[(ok[query] + ng[query]) / 2].emplace_back(query);
            }
            mid[i].clear();
        }
    }
    For(i,0,q) cout << (ok[i] < m ? ok[i] + 1 : -1) << endl;
}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}

Submission Info

Submission Time
Task H - Union Sets
User yahoobb
Language C++ (GCC 9.2.1)
Score 0
Code Size 1133 Byte
Status RE
Exec Time 295 ms
Memory 18916 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 19
WA × 12
RE × 18
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 8 ms 3604 KB
sample_02.txt AC 2 ms 3496 KB
sample_03.txt AC 3 ms 3600 KB
subtask_1_1.txt AC 3 ms 3496 KB
subtask_1_10.txt WA 43 ms 4956 KB
subtask_1_11.txt RE 181 ms 11776 KB
subtask_1_12.txt AC 6 ms 3652 KB
subtask_1_13.txt AC 9 ms 3644 KB
subtask_1_14.txt AC 3 ms 3572 KB
subtask_1_15.txt WA 69 ms 5596 KB
subtask_1_16.txt WA 11 ms 3708 KB
subtask_1_17.txt AC 28 ms 3728 KB
subtask_1_18.txt RE 113 ms 3244 KB
subtask_1_19.txt RE 116 ms 3892 KB
subtask_1_2.txt AC 8 ms 3496 KB
subtask_1_20.txt AC 4 ms 3656 KB
subtask_1_21.txt RE 117 ms 3724 KB
subtask_1_22.txt AC 9 ms 3748 KB
subtask_1_23.txt RE 155 ms 7212 KB
subtask_1_24.txt RE 157 ms 8468 KB
subtask_1_25.txt RE 159 ms 9596 KB
subtask_1_26.txt RE 172 ms 11452 KB
subtask_1_27.txt WA 295 ms 15900 KB
subtask_1_28.txt WA 295 ms 15872 KB
subtask_1_29.txt RE 157 ms 7228 KB
subtask_1_3.txt AC 4 ms 3520 KB
subtask_1_30.txt RE 157 ms 8576 KB
subtask_1_31.txt RE 159 ms 9732 KB
subtask_1_32.txt RE 170 ms 11464 KB
subtask_1_33.txt WA 292 ms 15532 KB
subtask_1_34.txt WA 293 ms 15680 KB
subtask_1_35.txt RE 151 ms 7284 KB
subtask_1_36.txt RE 156 ms 8468 KB
subtask_1_37.txt RE 159 ms 9752 KB
subtask_1_38.txt RE 169 ms 11560 KB
subtask_1_39.txt WA 290 ms 18828 KB
subtask_1_4.txt AC 14 ms 4008 KB
subtask_1_40.txt WA 292 ms 18916 KB
subtask_1_41.txt RE 133 ms 5792 KB
subtask_1_42.txt WA 174 ms 6740 KB
subtask_1_43.txt WA 249 ms 13700 KB
subtask_1_44.txt WA 273 ms 15148 KB
subtask_1_45.txt AC 162 ms 5300 KB
subtask_1_46.txt AC 183 ms 5752 KB
subtask_1_5.txt AC 40 ms 5128 KB
subtask_1_6.txt AC 9 ms 3704 KB
subtask_1_7.txt AC 2 ms 3628 KB
subtask_1_8.txt AC 2 ms 3648 KB
subtask_1_9.txt RE 117 ms 3688 KB