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

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 2019-12-05 11:49:50+0900 H - Union Sets hamuhei4869 C++14 (GCC 5.4.1) 600 3907 Byte AC 313 ms 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
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