PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
0-1 BFS (or Dijkstra)
PROBLEM:
A rook on an undirected graph moves as follows:
- if it’s currently on vertex u, pick an integer 1 \leq d \leq deg(u).
- Then, move to the d-th neighbor (in sorted order) of the current node as many times as it likes (as long as said d-th neighbor exists, of course).
Given a graph, a source vertex S and a target vertex T, find the minimum number of rook moves needed to move from S to T.
EXPLANATION:
As a first step, we of course sort the neighbors of every vertex.
Now, to do anything we need a nice way to model the movement of this rook.
Let’s split our graph into N layers.
On the i-th layer, each vertex u only has a directed edge to its i-th neighbor.
For convenience, let u_i denote the copy of vertex u on the i-th layer.
Then, the movement of the rook looks as follows:
- Let the current vertex be u.
- Choose any layer, then start at u_i and move freely along the directed edges in this layer.
This can be thought of as the directed edges within a layer having zero weight.
To model the “choose any layer” step, we can add a “base layer” (with the copy of vertex u in this layer denoted u_0), and add the following edges:
- u_0 \to u_i for each i \gt 0, with weight 1.
- u_i \to u_0 for each i\gt 0, with weight 0.
Then, for a given source vertex S and target vertex T, observe that the value we’re looking for is simply the shortest path from S_0 to T_0 in our weighted graph!
Of course, the main issue now is that this new graph is simply way too large: after all, with N+1 layers and N vertices in each, we have more than N^2 vertices!
However, observe that most of them don’t really matter.
For a vertex u, if i \gt deg(u) then vertex u_i doesn’t really matter much since we can’t move out from it in the i-th layer.
So, let’s modify our graph a bit as follows:
- For each u, if d = deg(u), keep only the vertices u_0, u_1, \ldots, u_d.
- For each 1 \leq i \leq d, suppose we want the edge u_i \to v_i.
Then, if i is larger than deg(v), “short circuit” the edge and direct it to v_0 instead (since in the old graph, the only outgoing edge from v_i is a 0-weight edge to v_0 anyway). - Add the u_0 \to u_i and u_i \to u_0 edges as described earlier.
This new graph has N + 2M vertices and 6M directed edges, which is pretty small!
Now, finding the shortest path from S_0 to T_0 is quite feasible.
Since all the weights are either 0 or 1, it’s possible to use 0-1 BFS for a linear time solution, though Dijkstra’s algorithm with an extra log factor should AC too.
TIME COMPLEXITY:
\mathcal{O}((N+M)\log(N+M)) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1e9+7;
#ifdef ANI
#include "D:/DUSTBIN/local_inc.h"
#else
#define dbg(...) 0
#endif
class Testcase{
public:
ll n,x,y,ans=-1;
vector<array<ll,2>> edges;
vector<vector<ll>> e;
vector<ll> dist;
Testcase(vector<vector<ll>> e,ll n,ll x,ll y=-1) {
this->e=e; this->n=n; this->x=x; this->y=y;
for(ll i=0;i<n;i++) {
for(ll j:e[i]) {
if(j>i) {
edges.push_back({i,j});
}
}
}
solution();
}
Testcase(vector<array<ll,2>> edges,ll n,ll x,ll y=-1) {
e.resize(n);
this->n=n; this->x=x; this->y=y; this->edges=edges;
sort(edges.begin(),edges.end());
for(auto z:edges) {
e[z[0]].push_back(z[1]);
e[z[1]].push_back(z[0]);
}
solution();
}
ll solution() {
vector<vector<ll>> dp(n);
for(ll i=0;i<n;i++) {
dp[i].resize(e[i].size()+1,inf);
sort(e[i].begin(),e[i].end());
}
dp[x][0]=0;
deque<array<ll,2>> dq;
dq.push_back({x,0});
while(!dq.empty()) {
ll cur=dq.front()[0],dir=dq.front()[1];
dq.pop_front();
if(dir!=0) {
// we go to the dir_th node in the edgelist of cur
ll to=e[cur][dir-1];
ll ndir=(e[to].size()>=dir?dir:0);
if(dp[cur][dir]<dp[to][ndir]) {
dp[to][ndir]=dp[cur][dir];
dq.push_front({to,ndir});
}
// stop
if(dp[cur][dir]<dp[cur][0]) {
dp[cur][0]=dp[cur][dir];
dq.push_front({cur,0});
}
continue;
}
/*
if dir is 0, we have a cost of 1
*/
for(ll i=1;i<=e[cur].size();i++) {
if(dp[cur][0]+1<dp[cur][i]) {
dp[cur][i]=dp[cur][0]+1;
dq.push_back({cur,i});
}
}
}
dist=vector<ll>(n,inf);
for(ll i=0;i<n;i++) {
for(ll j=0;j<=e[i].size();j++) {
dist[i]=min(dist[i],dp[i][j]);
}
}
if(y==-1) {
y=0;
for(ll i=0;i<n;i++) {
if(dist[i]>dist[y]) {
y=i;
}
}
}
return ans=dist[y];
}
void write(ofstream &inp, ofstream &out) {
if(ans<0) {
cerr<<"call solution"<<endl; exit(0);
}
inp<<n<<" "<<edges.size()<<" "<<x+1<<" "<<y+1<<"\n";
for(auto el:edges) {
inp<<el[0]+1<<" "<<el[1]+1<<"\n";
}
out<<ans<<"\n";
}
};
void main_() {
ll t; cin>>t;
assert(t<=1e4);
ll nsum=0,msum=0;
while(t--) {
ll n,m,x,y; cin>>n>>m>>x>>y;
nsum+=n; msum+=m;
assert(x!=y);
x--;y--;
vector<array<ll,2>> edges(m);
for(ll i=0;i<m;i++) {
cin>>edges[i][0]>>edges[i][1];
edges[i][0]--; edges[i][1]--;
}
cout<<Testcase(edges,n,x,y).solution()<<"\n";
}
assert(nsum<=3e5 && msum<=3e5);
}
int main() {
main_();
return 0;
}
Tester's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
// #define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=300005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
int32_t main()
{
IOS;
int t;
cin>>t;
while(t--)
{
int n, m, x, y;
cin>>n>>m;
cin>>x>>y;
vi v[n+1];
int deg[n+1];
fill(deg, 0);
rep(i,0,m)
{
int a, b;
cin>>a>>b;
v[a].pb(b);
v[b].pb(a);
deg[a]++;
deg[b]++;
}
rep(i,1,n+1)
sort(all(v[i]));
map <pii, int> mp;
set <pii> vis;
mp[{x, 0}]=0;
deque <pii> q;
q.pb({x, 0});
while(!q.empty())
{
pii p=q.front();
q.pop_front();
// if(vis.find(p) != vis.end())
// continue;
// vis.insert(p);
int u=p.ff, d=p.ss;
int cur = mp[{u, d}];
if(mp.find({u, 0})==mp.end() || mp[{u, 0}]>cur)
{
mp[{u, 0}]=cur;
q.push_front({u, 0});
}
if(d==0)
{
for(int i=0;i<deg[u];i++)
{
int to=v[u][i];
int d2=i+1;
if(d2>deg[to])
d2=0;
if(mp.find({to, d2})==mp.end() || mp[{to, d2}]>cur+1)
{
mp[{to, d2}]=cur+1;
q.push_back({to, d2});
}
}
}
else
{
int to=v[u][d-1];
int d2=d;
if(d2>deg[to])
d2=0;
if(mp.find({to, d2})==mp.end() || mp[{to, d2}]>cur)
{
mp[{to, d2}]=cur;
q.push_front({to, d2});
}
}
}
cout<<mp[{y, 0}]<<"\n";
}
}
Editorialist's code (Python)
import sys
input = sys.stdin.readline
from collections import deque
for _ in range(int(input())):
n, m, s, t = map(int, input().split())
adj = [ [] for _ in range(n+1)]
for i in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
# For each u, one vertex for each (u, d) s.t 0 <= d <= deg(u) -> N+M vertices
# (u, d) -> (v, d) with weight 0 (if it exists, (v, 0) otherwise)
# (u, 0) -> (u, d) with weight 1
# Find shortest path from (src, 0) to (tgt, 0)
newadj = [ [] for _ in range(n+2*m+1)]
st = [0]*(n+1)
for i in range(2, n+1):
st[i] = st[i-1] + len(adj[i-1]) + 1
for u in range(1, n+1):
adj[u].sort()
pos = st[u]
for j in range(len(adj[u])):
v = adj[u][j]
if len(adj[v]) >= j+1: newadj[pos + j + 1].append((st[v] + j + 1, 0))
else: newadj[pos + j + 1].append((st[v], 0))
for j in range(len(adj[u])):
newadj[pos].append((pos + j + 1, 1))
newadj[pos + j + 1].append((pos, 0))
dq = deque()
dist = [10**9]*(n+2*m+1)
dist[st[s]] = 0
dq.append(st[s])
while len(dq):
u = dq.pop()
for v, w in newadj[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
if w == 1: dq.appendleft(v)
else: dq.append(v)
print(dist[st[t]])