Submission #210611

#	Time	Username	Problem	Language	Result	Execution time	Memory
210611		tatyam	Robots (APIO13_robots)	C++17	60 / 100	1606 ms	130012 KiB

robots

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tuplis = array<int, 3>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
#define overload4(_1,_2,_3,_4,name,...) name
#define rep1(n) for(int i=0;i<n;++i)
#define rep2(i,n) for(int i=0;i<n;++i)
#define rep3(i,a,b) for(int i=a;i<b;++i)
#define rep4(i,a,b,c) for(int i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i : a)
#define aint(a) begin(a), end(a)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int INF = 0x33333333;
 
 
int n, w, h;
pii mem[500][500][4];
char s[501][501];
vector<pii> g[500][500];
int cost[10][10][500][500];
pii dfs(int x, int y, int d){
    if(x < 0) return {x + 1, y};
    if(y < 0) return {x, y + 1};
    if(x >= h) return {x - 1, y};
    if(y >= w) return {x, y - 1};
    if(s[x][y] == 'x') return {x + dx[d ^ 2], y + dy[d ^ 2]};
    if(mem[x][y][d] != pii{-1, -1}) return mem[x][y][d];
    int d2 = d;
    if(s[x][y] == 'A'){
        d2 += 3;
        d2 &= 3;
    }
    else if(s[x][y] == 'C'){
        d2 += 1;
        d2 &= 3;
    }
    mem[x][y][d] = {-2, -2};
    return mem[x][y][d] = dfs(x + dx[d2], y + dy[d2], d2);
}
void dijkstra(int from, int to){
    auto c = cost[from][to];
    rep(cen, from + 1, to) rep(h) rep(j, w) chmin(c[i][j], cost[from][cen][i][j] + cost[cen][to][i][j]);
    pq<tuplis> q;
    rep(h) rep(j, w) q.push({c[i][j], i, j});
    while(q.size()){
        auto [cost, x, y] = q.top();
        q.pop();
        for(auto [x2, y2] : g[x][y]) if(chmin(c[x2][y2], cost + 1)) q.push({c[x2][y2], x2, y2});
    }
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    memset(mem, 0xff, sizeof(mem));
    memset(cost, 0x33, sizeof(cost));
    cin >> n >> w >> h;
    rep(h) cin >> s[i];
    rep(h) rep(j, w) rep(d, 4) dfs(i, j, d);
    rep(h) rep(j, w) rep(d, 4) if(mem[i][j][d] != pii{-2, -2} && mem[i][j][d] != pii{i, j}) g[i][j].push_back(mem[i][j][d]);
    rep(h) rep(j, w) if(isdigit(s[i][j]))cost[s[i][j] - '1'][s[i][j] - '0'][i][j] = 0;
    rep(i, 1, n + 1) rep(j, 0, n + 1 - i) dijkstra(j, j + i);
    int ans = INF;
    rep(h) rep(j, w) chmin(ans, cost[0][n][i][j]);
    if(ans == INF) ans = -1;
    cout << ans << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40