Submission #1241806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241806		Geforgs	Maze (JOI23_ho_t3)	C++20	27 / 100	127 ms	47516 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

ll get(ll x, vector<ll>& parent){
    if(parent[x] == x) return x;
    return parent[x] = get(parent[x], parent);
}

void unite(ll x, ll y, vector<ll>& parent){
    x = get(x, parent);
    y = get(y, parent);
    parent[x] = y;
}

void push(ll pos, ll r, ll c, vector<ll>& dis, queue<ll>& q){
    ll x = pos/c, y = pos%c;
    if(x < r-1 and dis[pos + c] > dis[pos]){
        dis[pos + c] = dis[pos];
        q.push(pos + c);
    }
    if(x > 0 and dis[pos - c] > dis[pos]){
        dis[pos - c] = dis[pos];
        q.push(pos - c);
    }
    if(y < c-1 and dis[pos+1] > dis[pos]){
        dis[pos+1] = dis[pos];
        q.push(pos+1);
    }
    if(y > 0 and dis[pos-1] > dis[pos]){
        dis[pos-1] = dis[pos];
        q.push(pos-1);
    }
}

void push2(ll pos, ll r, ll c, ll n, vector<ll>& dis, queue<ll>& q, vector<ll>& parent, vector<ll>& parent2){
    ll x = pos/c, y = pos%c, curX, curY, nextX, nextY, nextPos, endPos;
    curX = max(0ll, x - n);
    curY = max(0ll, y - n + 1);
    nextY = min(c-1, curY + 2*n - 2);
    nextPos = curX*c + curY;
    nextPos = get(nextPos, parent);
    endPos = curX*c + nextY;
    while(true){
        if(nextPos >= endPos){
            if(dis[endPos] > dis[pos] + 1){
                dis[endPos] = dis[pos] + 1;
                q.push(endPos);
            }
            break;
        }
        if(dis[nextPos] > dis[pos] + 1){
            dis[nextPos] = dis[pos] + 1;
            q.push(nextPos);
        }
        unite(nextPos, nextPos+1, parent);
        nextPos = get(nextPos, parent);
    }
    curX = min(r-1, x + n);
    nextPos = curX*c + curY;
    nextPos = get(nextPos, parent);
    endPos = curX*c + nextY;
    while(true){
        if(nextPos >= endPos){
            if(dis[endPos] > dis[pos] + 1){
                dis[endPos] = dis[pos] + 1;
                q.push(endPos);
            }
            break;
        }
        if(dis[nextPos] > dis[pos] + 1){
            dis[nextPos] = dis[pos] + 1;
            q.push(nextPos);
        }
        unite(nextPos, nextPos+1, parent);
        nextPos = get(nextPos, parent);
    }
    curX = max(0ll, x - n + 1);
    curY = max(0ll, y - n);
    nextX = min(r-1, curX + 2*n - 2);
    nextPos = curX*c + curY;
    nextPos = get(nextPos, parent2);
    endPos = nextX*c + curY;
    while(true){
        if(nextPos >= endPos){
            if(dis[endPos] > dis[pos] + 1){
                dis[endPos] = dis[pos] + 1;
                q.push(endPos);
            }
            break;
        }
        if(dis[nextPos] > dis[pos] + 1){
            dis[nextPos] = dis[pos] + 1;
            q.push(nextPos);
        }
        unite(nextPos, nextPos+c, parent2);
        nextPos = get(nextPos, parent2);
    }
    curY = min(c-1, y + n);
    nextPos = curX*c + curY;
    nextPos = get(nextPos, parent2);
    endPos = nextX*c + curY;
    while(true){
        if(nextPos >= endPos){
            if(dis[endPos] > dis[pos] + 1){
                dis[endPos] = dis[pos] + 1;
                q.push(endPos);
            }
            break;
        }
        if(dis[nextPos] > dis[pos] + 1){
            dis[nextPos] = dis[pos] + 1;
            q.push(nextPos);
        }
        unite(nextPos, nextPos+c, parent2);
        nextPos = get(nextPos, parent2);
    }
}

void solve(){
    ll r, c, n, startR, startC, finishR, finishC, i, j, pos, distance=0;
    char x;
    cin>>r>>c>>n>>startR>>startC>>finishR>>finishC;
    --startR;
    --startC;
    --finishR;
    --finishC;
    vector<ll> a(r*c);
    vector<ll> dis(r*c, inf);
    vector<ll> parent(r*c);
    vector<ll> parent2(r*c);
    for(i=0;i<r;++i){
        for(j=0;j<c;++j){
            cin>>x;
            a[i*c + j] = x == '.';
            parent[i*c + j] = i*c + j;
            parent2[i*c + j] = i*c + j;
        }
    }
    queue<ll> q1, q2;
    dis[startR*c + startC] = 0;
    q1.push(startR*c + startC);
    while(!q1.empty()){
        while(!q1.empty()){
            pos = q1.front();
            q1.pop();
            if(dis[pos] < distance) continue;
            if(a[pos]){
                push(pos, r, c, dis, q1);
            }else{
                push2(pos, r, c, n, dis, q2, parent, parent2);
            }
        }
        ++distance;
        swap(q1, q2);
    }
    for(i=max(0ll, finishR-n+1);i<min(r-1, finishR+n-1);++i){
        for(j=max(0ll, finishC-n+1);j<min(c-1, finishC+n-1);++j){
            dis[finishR*c + finishC] = min(dis[finishR*c + finishC], dis[i*c+j] + 1);
        }
    }
    cout<<dis[finishR*c + finishC]<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6