Submission #746537

#	Time	Username	Problem	Language	Result	Execution time	Memory
746537		ThMinh_	Maze (JOI23_ho_t3)	C++14	100 / 100	1665 ms	434868 KiB

Main

#include<bits/stdc++.h>
#define forin(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N = 6e6 + 10;
int r, c, n, x, y, u, v, dp;
int row[4] = {0, -1, 0, 1};
int col[4] = {1, 0, -1, 0};
string s[N];
vector<vector<int>> f, par1, par2, vis, red;
queue<pair<int, int>> tmp;
void create(vector<vector<int>> &a) {
    a.resize(r + 2);
    forin(i,1,r + 1) a[i].resize(c + 2);
}
int root1(int i, int j) {
    return (par1[i][j] == j) ? j : par1[i][j] = root1(i, par1[i][j]);
}
int root2(int i, int j) {
    return (par2[i][j] == i) ? i : par2[i][j] = root2(par2[i][j], j);
}
bool check(int i, int j) {
    if(i < 1 || r < i || j < 1 || c < j) return 0;
    return 1;
}
void up(int x, int y) {
    if(!check(x, y)) return;
    if(f[x][y]) return;
    f[x][y] = dp + 1;
    par1[x][y] = y + 1;
    par2[x][y] = x + 1;
    tmp.push({x, y});
}
void bfs(int x, int y, queue<pair<int, int>> &p) {
    queue<pair<int, int>> q;
    q.push({x, y});
    while(!q.empty()) {
        int x1, y1; tie(x1, y1) = q.front(); q.pop();
        f[x1][y1] = dp;
        forin(k,0,3) {
            int u1 = x1 + row[k];
            int v1 = y1 + col[k];
            if(!check(u1, v1) || red[u1][v1]) continue;
            if(s[u1][v1] != '.' && f[u1][v1] != dp) continue;
            red[u1][v1] = 1;
            if(s[u1][v1] == '.') up(u1, v1);
            p.push({u1, v1});
            q.push({u1, v1});
        }
    }
}
int main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("Task.inp","r")) {
        freopen("Task.inp","r",stdin);
        freopen("WA.out","w",stdout);
    }
    cin>>r>>c>>n;
    create(f);
    create(vis);
    create(red);
    cin>>x>>y;
    cin>>u>>v;
    forin(i,1,r) {
        cin>>s[i];
        s[i] = " " + s[i];
    }
    create(par1);
    create(par2);
    forin(i,1,r + 1) forin(j,1,c + 1) {
        par1[i][j] = j;
        par2[i][j] = i;
    }
    up(x, y);
    while(true) {
        dp++;
        queue<pair<int, int>> q;
        while(!tmp.empty()) {
            int x1, y1; tie(x1, y1) = tmp.front(); tmp.pop();
            if(red[x1][y1]) continue;
            red[x1][y1] = 1;
            q.push({x1, y1});
            bfs(x1, y1, q);
        }
        while(!q.empty()) {
            int x1, y1; tie(x1, y1) = q.front(); q.pop();
            vis[x1][y1] = 1;
            vector<int> vt;
            forin(k,0,3) {
                int u1 = x1 + row[k];
                int v1 = y1 + col[k];
                if(!check(u1, v1) || !vis[u1][v1]) continue;
                vt.push_back(k);
            }
            if(vt.empty()) {
                forin(i,-n,n) forin(j,-n,n) if(!(abs(i) == n && abs(j) == n) && check(x1 + i, y1 + j)) {
                    up(x1 + i, y1 + j);
                }
            }
            else if(vt.size() == 1) {
                int k = vt[0];
                int t = - (row[k] + col[k]);
                if(row[k]) {
                    up(x1 + t * (n - 1), y1 + n);
                    up(x1 + t * (n - 1), y1 - n);
                    int u1 = x1 + t * n;
                    int v1 = max(1, y1 - n + 1);
                    if(!check(u1, v1)) continue;
                    while(true) {
                        v1 = root1(u1, v1);
                        if(v1 > min(c, y1 + n - 1)) break;
                        up(u1, v1);
                    }
                }
                else {
                    up(x1 + n, y1 + t * (n - 1));
                    up(x1 - n, y1 + t * (n - 1));
                    int u1 = max(1, x1 - n + 1);
                    int v1 = y1 + t * n;
                    if(!check(u1, v1)) continue;
                    while(true) {
                        u1 = root2(u1, v1);
                        if(u1 > min(r, x1 + n - 1)) break;
                        up(u1, v1);
                    }
                }
            }
            else if(vt.size() == 2 && (vt[0] - vt[1]) % 2) {
                    if(vt[0] % 2) swap(vt[0], vt[1]);
                    int t1 = - (row[vt[1]] + col[vt[1]]);
                    int t2 = - (row[vt[0]] + col[vt[0]]);
                    up(x1 + t1 * (n - 1), y1 + n);
                    up(x1 + t1 * (n - 1), y1 - n);
                    up(x1 + n, y1 + t2 * (n - 1));
                    up(x1 - n, y1 + t2 * (n - 1));
            }
            else {
                forin(k,0,3) up(x1 + row[k] * n, y1 + col[k] * n);
            }
        }
        if(f[u][v]) return cout<<f[u][v] - 1, 0;
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("Task.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("WA.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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: 6 / 6