Submission #1019016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019016		andrei_iorgulescu	Maze (JOI23_ho_t3)	C++17	94 / 100	955 ms	282196 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

int inf = 1e9;
int dl[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};

int r,c,n;
int xs,ys,xf,yf;
vector<vector<char>>a;
vector<vector<int>>d;
pair<short int,int> new_cells[6000005],cells[6000005];
int ncs,cs;
vector<vector<int>>s;
vector<vector<short int>>ss;
vector<int>ts;
vector<short int>tss;
int lgc,lgr;

void updates(int unde,int pos)
{
    ts[unde]--;
    #pragma GCC ivdep
    for (int i = pos; i <= c; i += (i & -i))
        s[unde][i]--;
}

void updatess(int unde,int pos)
{
    tss[unde]--;
    #pragma GCC ivdep
    for (int i = pos; i <= r; i += (i & -i))
        ss[unde][i]--;
}

int querys(int x,int y)
{
    int rsp = 0;
    #pragma GCC ivdep
    for (int i = y; i > 0; i -= (i & -i))
        rsp += s[x][i];
    return rsp;
}

int queryss(int x,int y)
{
    int rsp = 0;
    #pragma GCC ivdep
    for (int i = y; i > 0; i -= (i & -i))
        rsp += ss[x][i];
    return rsp;
}

int s_findnext(int x,int y)
{
    int vv = querys(x,y - 1);
    if (vv == ts[x])
        return -1;
    int sumaib = 0;
    int st = 0,pas = 1 << lgc;
    #pragma GCC ivdep
    while (pas != 0)
    {
        if (st + pas <= c and sumaib + s[x][st + pas] <= vv)
        {
            st += pas;
            sumaib += s[x][st];
        }
        pas >>= 1;
    }
    return st + 1;
}

int ss_findnext(int x,int y)
{
    int vv = queryss(x,y - 1);
    if (vv == tss[x])
        return -1;
    int sumaib = 0;
    int st = 0,pas = 1 << lgr;
    #pragma GCC ivdep
    while (pas != 0)
    {
        if (st + pas <= r and sumaib + ss[x][st + pas] <= vv)
        {
            st += pas;
            sumaib += ss[x][st];
        }
        pas >>= 1;
    }
    return st + 1;
}

void dfs(int x,int y)
{
    //cout << "sus" << x << ' ' << y << endl;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dl[i],ny = y + dc[i];
        if (nx >= 1 and nx <= r and ny >= 1 and ny <= c and d[nx][ny] == inf and a[nx][ny] == '.')
        {
            d[nx][ny] = d[x][y];
            //s[nx].erase(ny);
            //ss[ny].erase(nx);
            if (ny % 4 != 0 or r * c <= 3000000)
                updates(nx,ny);
            if (nx % 4 != 0 or r * c <= 3000000)
                updatess(ny,nx);
            cells[cs++] = {nx,ny};
            dfs(nx,ny);
        }
    }
}

int dgl;

void orizontala(int x,int y1,int y2)
{
    //cout << "h" << x << ' ' << y1 << ' ' << y2 << endl;
    #pragma GCC ivdep
    while (true)
    {
        /*auto it = s[x].lower_bound(y1);
        if (it == s[x].end() or *it > y2)
            return;
        d[x][*it] = dgl;
        new_cells.push_back({x,*it});
        s[x].erase(*it);
        ss[*it].erase(x);*/
        int it = s_findnext(x,y1);
        if (it == -1 or it > y2)
            return;
        d[x][it] = dgl;
        new_cells[ncs++] = {x,it};
        if (it % 4 != 0 or r * c <= 3000000)
            updates(x,it);
        if (x % 4 != 0 or r * c <= 3000000)
            updatess(it,x);
    }
}

void verticala(int y,int x1,int x2)
{
    //cout << "v" << y << ' ' << x1 << ' ' << x2 << endl;
    #pragma GCC ivdep
    while (true)
    {
        /*auto it = ss[y].lower_bound(x1);
        if (it == ss[y].end() or *it > x2)
            return;
        d[*it][y] = dgl;
        new_cells.push_back({*it,y});
        ss[y].erase(*it);
        s[*it].erase(y);*/
        int it = ss_findnext(y,x1);
        if (it == -1 or it > x2)
            return;
        d[it][y] = dgl;
        new_cells[ncs++] = {it,y};
        if (it % 4 != 0 or r * c <= 3000000)
            updatess(y,it);
        if (y % 4 != 0 or r * c <= 3000000)
            updates(it,y);
    }
}

void baga(int x,int y)
{
    //cout << "bagat" << ' ' << x << ' ' << y << endl;
    dgl = d[x][y] + 1;
    if (abs(x - xf) <= n and abs(y - yf) <= n and abs(x - xf) + abs(y - yf) < 2 * n)
    {
        d[xf][yf] = min(d[xf][yf],1 + d[x][y]);
        return;
    }
    int x1 = x - n,x2 = x + n,y1 = y - n,y2 = y + n;
    ///teoretic pot tot patratul (x1,y1,x2,y2) fara colturi, daca ies din matrice ayaye
    ///pot sa iau intersectia dreptunghiurilor (x1,y1,x2,y2) cu matricea si daca e tai colturile
    x1 = max(x1,1);
    x2 = min(x2,r);
    y1 = max(y1,1);
    y2 = min(y2,c);
    //cout << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << endl;
    if (x1 != x - n)
        orizontala(x1,y1,y2);
    else
    {
        int y1r = y1,y2r = y2;
        if (y1 == y - n)
            y1r++;
        if (y2 == y + n)
            y2r--;
        orizontala(x1,y1r,y2r);
    }
    if (x2 != x + n)
        orizontala(x2,y1,y2);
    else
    {
        int y1r = y1,y2r = y2;
        if (y1 == y - n)
            y1r++;
        if (y2 == y + n)
            y2r--;
        orizontala(x2,y1r,y2r);
    }
    if (y1 != y - n)
        verticala(y1,x1,x2);
    else
    {
        int x1r = x1,x2r = x2;
        if (x1 == x - n)
            x1r++;
        if (x2 == x + n)
            x2r--;
        verticala(y1,x1r,x2r);
    }
    if (y2 != y + n)
        verticala(y2,x1,x2);
    else
    {
        int x1r = x1,x2r = x2;
        if (x1 == x - n)
            x1r++;
        if (x2 == x + n)
            x2r--;
        verticala(y2,x1r,x2r);
    }
}

int m4(int l,int r)
{
    return r / 4 - (l - 1) / 4;
}

int main()
{
    srand(time(NULL));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> r >> c >> n >> xs >> ys >> xf >> yf;
    a.resize(r + 1);
    s.resize(r + 1);
    ss.resize(c + 1);
    ts.resize(r + 1);
    tss.resize(c + 1);
    lgc = __lg(c);
    lgr = __lg(r);
    for (int i = 1; i <= r; i++)
        ts[i] = c;
    for (int i = 1; i <= c; i++)
        tss[i] = r;
    for (int i = 1; i <= r; i++)
        s[i].resize(c + 1);
    for (int i = 1; i <= c; i++)
        ss[i].resize(r + 1);
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            s[i][j] = (j & -j);
            ss[j][i] = (i & -i);
        }
    }
    if (r * c > 3000000)
    {
        for (int i = 1; i <= r; i++)
        {
            for (int j = 1; j <= c; j++)
            {
                int ct_rele = m4(j - (j & -j) + 1,j);
                s[i][j] -= ct_rele;
                ct_rele = m4(i - (i & -i) + 1,i);
                ss[i][j] -= ct_rele;
            }
        }
    }
    for (int i = 1; i <= r; i++)
    {
        a[i].resize(c + 1);
        for (int j = 1; j <= c; j++)
            cin >> a[i][j];
    }
    d.resize(r + 1);
    for (int i = 1; i <= r; i++)
        d[i].resize(c + 1);
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            d[i][j] = 1e9;
    if (r * c <= 6000000)
    {
        new_cells[ncs++] = {xs,ys};
        d[xs][ys] = 0;
        if (ys % 4 != 0 or r * c <= 3000000)
            updates(xs,ys);
        if (xs % 4 != 0 or r * c <= 3000000)
            updatess(ys,xs);
        while (true)
        {
            //cout << endl;
            //for (auto it : new_cells)
              //  cout << "nc" << ' ' << it.first << ' ' << it.second << ' ' << d[it.first][it.second] << endl;
            //cells = new_cells;
            cs = ncs;
            for (int i = 0; i < cs; i++)
                cells[i] = new_cells[i];
            for (int i = 0; i < ncs; i++)
                dfs(new_cells[i].first,new_cells[i].second);
            if (d[xf][yf] != inf)
                break;
            ncs = 0;
            for (int i = 0; i < cs; i++)
                baga(cells[i].first,cells[i].second);
            if (d[xf][yf] != inf)
                break;
        }
        cout << d[xf][yf];
    }
    return 0;
}

/**
din (i,j) pot merge ori intr-un vecin care e si el alb
as mai putea merge in patratul de latura 2n + 1 centrat in (i,j) fara colturile lui
acum, faza funny e ca nu prea ma intereseaza de mersul inauntrul formei ci doar pe marini, unless este celula de finish in interior
asa ca, ori e celula de finish in interior si zic direct gen "boss, dute in aia", ori pun cu cost + 1 celulele de pe margini
acum, ca sa gasesc celulele de pe margini nevizitate inca, trebuie doar sa vad pe niste bucati de linii / coloane care mai sunt alive
asta pot cu un set, dar cu constanta aia :skull: mai bine nu, deci bag aib si cb pe aib

Acum, cum imi fac dfs-ul ca sa nu iasa nimic dubios
In etape, cat timp n-am ajuns la finish, mai intai imi iau celulele cu care n-am trecut prin faza 1 si le dau fill cat au in jur 0
Iar in faza 2 iau celulele care n-au trecut prin faza asta si le fac kinda patratul, iau alea de pe margini etc
**/

///hocus pocus ca sa treaca

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