はじめに
この記事は東京高専プロコンゼミ① Advent Calendar 2019の6日目の記事です。
ちょっと前から、精進で問題を解いたら記事にするというのをしていて、そのままアドベントカレンダーの記事も兼ねてしまおうみたいな魂胆です。
うちの部には非競プロerもいるので、いつもより丁寧に書きたいですが、あまり厳密な理解をしていなかったり、厳密な文章を書くのになれていなかったりで、おきもちを説明する感じになってしまいました。
問題URL
解法
並行二分探索をします。
並行二分探索は、二分探索する区間が同じなクエリ達の判定をまとめられるとき、それをまとめてしまうテク(?)のことをいうっぽいです。
問題の解き方を見るのが早い気がするので、解いてみます。
まず、クエリごとに問題を解いてみることを考えます。二分探索をすることを考えると 、
「番目までの操作を行ったときに
が同じ集合かどうか？」というようなことを考えて、
について二分探索を行えば良いです。
判定には番目までの操作をUnionFindで再現すると、
で行うことができます。
なので、1つのクエリについてで問題が解けます。(UnionFindで前からやるだけで二分探索がいらなくなりますが、ここでは考えないことにします)
この二分探索をQ個のクエリにそれぞれ行ってしまうと、もちろん間に合いません。
ここで、二分探索の判定部分に着目します。k番目までの操作をUnionFindで再現した場合、「が同じ集合に属するか？ 」という質問以外にも、任意の要素のペアについて同じ集合に属するか判定することができます。
この判定はまとめられそうです。
個のクエリをまとめてみます。以下のようにします。
- はじめに、すべてのクエリは1つの集合で、その集合には探索する区間[0, M)が紐付いているとします。
- UnionFindを用いて操作を前からシュミレートします。その途中で、条件を満たすようなクエリの集合について適宜以下のような操作を行います。
- 2でk番目までの操作が終わったとき、そのkが区間の中央になるような集合について考えます。その集合の要素であるクエリそれぞれについて判定をして、その結果で集合を2つに分割します。分割後のクエリの集合には判定の結果ごとに、二分探索と同じように新しい探索区間が紐付けられます。(片方は
、もう片方は
みたいな具合に)
- クエリ達の持つ探索区間が十分に小さくなるまでクエリの集合たちに対して2~3の分割を繰り返します。
セグメント木の図みたいなものを思い浮かべてみるとクエリ分割のおきもちはわかりやすいです。
このようにすると、クエリを分割するために行うシュミレートの回数は回程度です。クエリを分割するシュミレートの計算量は、
になります。
なので、全体の計算量はになり、解けました。
個のクエリをまとめる部分が、並行二分探索と呼ばれているものみたいです。
参考にしたもの
https://youtu.be/NQhd1Ifkxtk これのD問題の解説がとてもわかりやすいです
ACしたコード
最後まで併合されないようなクエリについては二分探索の前に弾いています。
#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();
break;
}
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>>> range_front = range.front();
range.pop();
vector<pair<pair<ll, ll>, int>> ok;
vector<pair<pair<ll, ll>, int>> ng;
for(auto q : range_front.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(range_front.first.first, (range_front.first.first + range_front.first.second)/2), ok));
if(ng.size() != 0)next_range.push(make_pair(make_pair((range_front.first.first + range_front.first.second)/2, range_front.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;
}