oj.uz

Submission #210596

# Submission time Handle Problem Language Result Execution time Memory
210596 2020-03-17T19:42:02 Z tatyam Robots (APIO13_robots) C++17
60 / 100
 1500 ms 130172 KB 
#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, int cnt = 0){
    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];
    if(cnt > 1000000) return mem[x][y][d] = {-2, -2};
    int d2 = d;
    if(s[x][y] == 'A'){
        d2 += 3;
        d2 &= 3;
    }
    else if(s[x][y] == 'C'){
        d2 += 1;
        d2 &= 3;
    }
    return mem[x][y][d] = dfs(x + dx[d2], y + dy[d2], d2, cnt + 1);
}
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 111868 KB Output is correct
2 Correct 61 ms 111864 KB Output is correct
3 Correct 61 ms 111864 KB Output is correct
4 Correct 61 ms 111868 KB Output is correct
5 Correct 60 ms 111864 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 111868 KB Output is correct
2 Correct 61 ms 111864 KB Output is correct
3 Correct 61 ms 111864 KB Output is correct
4 Correct 61 ms 111868 KB Output is correct
5 Correct 60 ms 111864 KB Output is correct
6 Correct 62 ms 111864 KB Output is correct
7 Correct 60 ms 111864 KB Output is correct
8 Correct 61 ms 111864 KB Output is correct
9 Correct 63 ms 111864 KB Output is correct
10 Correct 61 ms 111864 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 111868 KB Output is correct
2 Correct 61 ms 111864 KB Output is correct
3 Correct 61 ms 111864 KB Output is correct
4 Correct 61 ms 111868 KB Output is correct
5 Correct 60 ms 111864 KB Output is correct
6 Correct 62 ms 111864 KB Output is correct
7 Correct 60 ms 111864 KB Output is correct
8 Correct 61 ms 111864 KB Output is correct
9 Correct 63 ms 111864 KB Output is correct
10 Correct 61 ms 111864 KB Output is correct
11 Correct 846 ms 118204 KB Output is correct
12 Correct 96 ms 117224 KB Output is correct
13 Correct 492 ms 118328 KB Output is correct
14 Correct 1251 ms 118204 KB Output is correct
15 Correct 790 ms 118244 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 111868 KB Output is correct
2 Correct 61 ms 111864 KB Output is correct
3 Correct 61 ms 111864 KB Output is correct
4 Correct 61 ms 111868 KB Output is correct
5 Correct 60 ms 111864 KB Output is correct
6 Correct 62 ms 111864 KB Output is correct
7 Correct 60 ms 111864 KB Output is correct
8 Correct 61 ms 111864 KB Output is correct
9 Correct 63 ms 111864 KB Output is correct
10 Correct 61 ms 111864 KB Output is correct
11 Correct 846 ms 118204 KB Output is correct
12 Correct 96 ms 117224 KB Output is correct
13 Correct 492 ms 118328 KB Output is correct
14 Correct 1251 ms 118204 KB Output is correct
15 Correct 790 ms 118244 KB Output is correct
16 Execution timed out 1587 ms 130172 KB Time limit exceeded
17 Halted 0 ms 0 KB -