Contest Duration: - (local time) (180 minutes)

Submission #19560092

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){
vector<vector<int>> nextmid(m+1);
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;
}
nextmid[(ok[query] + ng[query]) / 2].emplace_back(query);
}
}
swap(mid, nextmid);
}
For(i,0,q) cout << (ok[i] < m ? ok[i] + 1 : -1) << endl;
}
int main(){
Main();
/*
東方風神録は神が出てくるので当然神ゲー
*/
return 0;
}```

#### Submission Info

Submission Time 2021-01-22 13:47:34+0900 H - Union Sets yahoobb C++ (GCC 9.2.1) 600 1180 Byte AC 336 ms 13984 KB

#### 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
Case Name Status Exec Time Memory
sample_01.txt AC 5 ms 3612 KB
sample_02.txt AC 3 ms 3428 KB
sample_03.txt AC 2 ms 3464 KB
subtask_1_1.txt AC 2 ms 3564 KB
subtask_1_10.txt AC 47 ms 6476 KB
subtask_1_11.txt AC 185 ms 9824 KB
subtask_1_12.txt AC 10 ms 3684 KB
subtask_1_13.txt AC 13 ms 3812 KB
subtask_1_14.txt AC 6 ms 3600 KB
subtask_1_15.txt AC 70 ms 4588 KB
subtask_1_16.txt AC 16 ms 3716 KB
subtask_1_17.txt AC 28 ms 3876 KB
subtask_1_18.txt AC 3 ms 3620 KB
subtask_1_19.txt AC 27 ms 3916 KB
subtask_1_2.txt AC 4 ms 3568 KB
subtask_1_20.txt AC 4 ms 3524 KB
subtask_1_21.txt AC 20 ms 3624 KB
subtask_1_22.txt AC 5 ms 3592 KB
subtask_1_23.txt AC 206 ms 6540 KB
subtask_1_24.txt AC 207 ms 6292 KB
subtask_1_25.txt AC 207 ms 6592 KB
subtask_1_26.txt AC 218 ms 7340 KB
subtask_1_27.txt AC 336 ms 12180 KB
subtask_1_28.txt AC 334 ms 12040 KB
subtask_1_29.txt AC 205 ms 6452 KB
subtask_1_3.txt AC 3 ms 3512 KB
subtask_1_30.txt AC 205 ms 6544 KB
subtask_1_31.txt AC 209 ms 6340 KB
subtask_1_32.txt AC 219 ms 7488 KB
subtask_1_33.txt AC 319 ms 12572 KB
subtask_1_34.txt AC 317 ms 12368 KB
subtask_1_35.txt AC 201 ms 6456 KB
subtask_1_36.txt AC 199 ms 6356 KB
subtask_1_37.txt AC 201 ms 6652 KB
subtask_1_38.txt AC 212 ms 7504 KB
subtask_1_39.txt AC 335 ms 13900 KB
subtask_1_4.txt AC 26 ms 3996 KB
subtask_1_40.txt AC 334 ms 13984 KB
subtask_1_41.txt AC 189 ms 6032 KB
subtask_1_42.txt AC 199 ms 6220 KB
subtask_1_43.txt AC 266 ms 10204 KB
subtask_1_44.txt AC 298 ms 12104 KB
subtask_1_45.txt AC 164 ms 5228 KB
subtask_1_46.txt AC 184 ms 5608 KB
subtask_1_5.txt AC 46 ms 6072 KB
subtask_1_6.txt AC 7 ms 3764 KB
subtask_1_7.txt AC 4 ms 3472 KB
subtask_1_8.txt AC 4 ms 3656 KB
subtask_1_9.txt AC 48 ms 3796 KB