oj.uz

Submission #210611

# Submission time Handle Problem Language Result Execution time Memory
210611 2020-03-17T20:56:45 Z tatyam Robots (APIO13_robots) C++17
60 / 100
 1500 ms 130012 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){
    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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 111864 KB Output is correct
2 Correct 71 ms 111864 KB Output is correct
3 Correct 59 ms 111864 KB Output is correct
4 Correct 60 ms 111864 KB Output is correct
5 Correct 60 ms 111820 KB Output is correct
6 Correct 58 ms 111864 KB Output is correct
7 Correct 59 ms 111864 KB Output is correct
8 Correct 73 ms 111864 KB Output is correct
9 Correct 60 ms 111864 KB Output is correct
10 Correct 58 ms 111864 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 111864 KB Output is correct
2 Correct 71 ms 111864 KB Output is correct
3 Correct 59 ms 111864 KB Output is correct
4 Correct 60 ms 111864 KB Output is correct
5 Correct 60 ms 111820 KB Output is correct
6 Correct 58 ms 111864 KB Output is correct
7 Correct 59 ms 111864 KB Output is correct
8 Correct 73 ms 111864 KB Output is correct
9 Correct 60 ms 111864 KB Output is correct
10 Correct 58 ms 111864 KB Output is correct
11 Correct 868 ms 118212 KB Output is correct
12 Correct 96 ms 117228 KB Output is correct
13 Correct 491 ms 118284 KB Output is correct
14 Correct 1276 ms 118212 KB Output is correct
15 Correct 789 ms 118208 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 111864 KB Output is correct
2 Correct 71 ms 111864 KB Output is correct
3 Correct 59 ms 111864 KB Output is correct
4 Correct 60 ms 111864 KB Output is correct
5 Correct 60 ms 111820 KB Output is correct
6 Correct 58 ms 111864 KB Output is correct
7 Correct 59 ms 111864 KB Output is correct
8 Correct 73 ms 111864 KB Output is correct
9 Correct 60 ms 111864 KB Output is correct
10 Correct 58 ms 111864 KB Output is correct
11 Correct 868 ms 118212 KB Output is correct
12 Correct 96 ms 117228 KB Output is correct
13 Correct 491 ms 118284 KB Output is correct
14 Correct 1276 ms 118212 KB Output is correct
15 Correct 789 ms 118208 KB Output is correct
16 Execution timed out 1606 ms 130012 KB Time limit exceeded
17 Halted 0 ms 0 KB -