Time-7 - METEORITE

2 secs 1024 MB

matcharate12

Problem

Submissions

Test cases

Editorial

この問題は UnionFind(素集合データ構造)、逆の操作 を問います。

問題文では辺を削除する、といった操作が必要になりますが、この操作の実装は容易ではありません。
なので、次のように逆の操作をする方が良さそうです。

すべてのイベントが終わった後の状態のグラフを構築し、与えられるグラフの辺の情報を矛盾なく追加していく

「すべてのイベントが終わった後の状態」とは、辺の情報に頂点番号 $x_1,x_2,...,x_Q$ が含まれていた時、その辺は採用されていないグラフを言います。
その後、イベントでは $j=1,2,...,Q$ として行っていましたが、逆の操作のため $j'=Q,Q-1,Q-2,...,1$ の順で、次の操作を行います。

頂点 $x_{j'}$ をグラフに追加する、すなわち $x_{j'}$ を含む辺を追加していく

こうして操作後にできるグラフは入力に与えられたグラフと等しくなります。よってこの逆の操作が適切であることがわかります。

また $Q-j'(=j)$ 回目の操作毎に、毎回頂点 $1$ から頂点 $N$ へのパスの存在判定を、DFSなどの探索法を用いると最悪 $O(Q(N+M))$ だけかかり、時間制限に間に合いません。なのでこの判定を高速に行う必要があります。

そこで、伝家の宝刀であるUnionFind(素集合データ構造)を用いることで、この判定を $O(\alpha(N))$ ※で実装することができます。

最終的に答えるべき値は、この操作をはじめ、初めて頂点 $1$ から頂点 $N$ をつなぐパスが存在するときの $j'$ を $J$ とおくと、 $Q-J$ となります。なおこの判定がすべての $j'$ に対し、頂点 $1$ から頂点 $N$ をつなぐパスが存在するなら、答えは Reachable となります。

以上からこの問題は $O(M+Q\alpha(N))$ で実装することができました。以下が解答例になります。

C++

xxxxxxxxxx
 
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(A)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<int>>;
using EGraph = vector<Edge>;
using SGraph = vector<set<ll>>;
template <typename T>
int siz(T& a){ return (int)a.size(); }
using namespace std;
​
struct UnionFind {
    vector<int> par,rank,siz;
    UnionFind(int n):par(n,-1),rank(n,0),siz(n,1) {}
​
    int root(int x){
        if(par[x] == -1) return x;
        return par[x] = root(par[x]);
    }
​
    bool same(int x,int y){
        int rx = root(x),ry = root(y);
        return rx == ry;
    }
​
    bool unite(int x,int y){
        int rx = root(x),ry = root(y);
        if(rx == ry) return 0;
​
        //union by rank
        if(rank[rx] < rank[ry]) swap(rx,ry);
        par[ry] = rx;
        if(rank[ry] == rank[rx]) rank[rx]++;
        siz[rx] += siz[ry];
        return 1;
    }
​
    int size(int x){ return siz[root(x)]; }
};
​
int main(){
    int n,m,s,t; cin >> n >> m >> s >> t;
    s--; t--;
    Graph G(n);
    vector<P> p(m);
    rep(i,m){
        int a,b; cin >> a >> b;
        a--; b--;
        p[i] = {a,b};
        G[a].push_back(b);
        G[b].push_back(a);
    }
​
    int q; cin >> q;
    vector<P> Q;
    set<int> ok,ng;
    rep(i,q){
        int q; cin >> q;
        q--;
        if(ng.count(q)) continue;
        ng.insert(q);
        Q.push_back({q,i+1});
    }
​
    UnionFind uf(n);
    rep(i,m){
        if(!ng.count(p[i].first) && !ng.count(p[i].second)) uf.unite(p[i].first,p[i].second);
        if(!ng.count(p[i].first)) ok.insert(p[i].first);
        if(!ng.count(p[i].second)) ok.insert(p[i].second);
    }
​
    if(uf.same(s,t)){
        cout << "Reachable" << endl;
        return 0;
    }
    
    reverse(all(Q));
    rep(i,siz(Q)){
        ok.insert(Q[i].first);
        for(auto& g : G[Q[i].first]) if(ok.count(g)) uf.unite(Q[i].first,g);
​
        if(uf.same(s,t)){
            cout << Q[i].second;
            return 0;
        }
    }
    cout << 0 << endl;
}
​

Python

xxxxxxxxxx
 
class UnionFind():
    def __init__(self,n):
        self.siz = [1 for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
        self.par = [-1 for i in range(n+1)]
    
    def root(self,x):
        if self.par[x] == -1: return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
​
    def same(self,x,y):
        return self.root(x) == self.root(y)
    
    def unite(self,x,y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: return 0
        
        #union by rank
        if self.rank[rx] < self.rank[ry]: rx,ry = ry,rx
        self.par[ry] = rx
        if self.rank[ry] == self.rank[rx]: self.rank[rx] += 1
        self.siz[rx] += self.siz[ry]
        return 1
​
    def size(self,x):
        return self.siz[self.root(x)]
​
n,m,s,t = map(int,input().split())
s -= 1
t -= 1
​
G = [[] for i in range(n)]
p = [[] for i in range(m)]
​
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    p[i] = [a,b]
    G[a].append(b)
    G[b].append(a)
​
q = int(input())
Q = []
ok = []
ng = []
​
for i in range(q):
    qq = int(input())
    qq -= 1
    if qq in ng: continue
    ng.append(qq)
    Q.append([qq,i+1])
​
uf = UnionFind(n)
for i in range(m):
    if (not p[i][0] in ng and not p[i][1] in ng):
        uf.unite(p[i][0],p[i][1])
    if not p[i][0] in ng:
        ok.append(p[i][0])
    if not p[i][1] in ng:
        ok.append(p[i][1])
​
if uf.same(s,t):
    print("Reachable")
    exit()
    
Q.reverse()
for i in range(len(Q)):
    ok.append(Q[i][0])
    for g in G[Q[i][0]]:
        if g in ok: uf.unite(Q[i][0],g)
    
    if uf.same(s,t):
        print(Q[i][1])
        exit()
print(0)