oj.uz

Submission #246985

# Submission time Handle Problem Language Result Execution time Memory
246985 2020-07-10T17:08:08 Z keko37 Robots (APIO13_robots) C++14
60 / 100
 1500 ms 84084 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 505;

int n, h, w, sol = 1e9;
int robot[20];
char a[MAXN][MAXN];
pi nxt[MAXN*MAXN][4];
int to[MAXN*MAXN][4], bio[MAXN * MAXN];
int dist[MAXN * MAXN][10][10];
vector <int> v;
set <pi> st;
queue <int> q;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool ok (int x, int y) {
    return 0 <= x && x < h && 0 <= y && y < w;
}

void build_succesor () {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (a[i][j] == 'x') continue;
            for (int d = 0; d < 4; d++) {
                int nx, ny, nd;
                nd = (a[i][j] == 'A' ? (d + 3) % 4 : (a[i][j] == 'C' ? (d + 1) % 4 : d));
                nx = i + dx[nd];
                ny = j + dy[nd];
                if (!ok(nx, ny) || a[nx][ny] == 'x') {
                    nxt[i*w+j][d] = {i*w+j, -1};
                } else {
                    nxt[i*w+j][d] = {nx*w+ny, nd};
                }
            }
        }
    }
}

int get_sink (int node, int d) {
    if (to[node][d] >= 0) return to[node][d];
    to[node][d] = -2;
    if (nxt[node][d].second == -1) {
        return to[node][d] = nxt[node][d].first;
    } else {
        int succ = nxt[node][d].first, nd = nxt[node][d].second;
        if (to[succ][nd] == -2) {
            return to[node][d] = -3;
        } else {
            return to[node][d] = get_sink(succ, nd);
        }
    }
}

void build_graph () {
    memset(to, -1, sizeof to);
    for (int i = 0; i < n; i++) {
        q.push(robot[i]);
        bio[robot[i]] = 1;
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        v.push_back(x);
        for (int d = 0; d < 4; d++) {
            int sus = get_sink(x, d);
            if (!bio[sus]) {
                q.push(sus);
                bio[sus] = 1;
            }
        }
    }
}
void solve (int lo, int hi) {
    st.clear();
    for (auto x : v) dist[x][lo][hi] = 1e9;
    if (lo == hi) {
        dist[robot[lo]][lo][lo] = 0;
        st.insert({0, robot[lo]});
    } else {
        for (auto x : v) {
            for (int i = lo; i < hi; i++) {
                int val = dist[x][lo][i] + dist[x][i + 1][hi];
                dist[x][lo][hi] = min(dist[x][lo][hi], val);
            }
            if (dist[x][lo][hi] < 1e9) st.insert({dist[x][lo][hi], x});
        }
    }
    while (!st.empty()) {
        int x = st.begin() -> second;
        int len = st.begin() -> first;
        st.erase(st.begin());
        for (int d = 0; d < 4; d++) {
            int sus = to[x][d];
            if (sus < 0) continue;
            if (len + 1 < dist[sus][lo][hi]) {
                if (st.find({dist[sus][lo][hi], sus}) != st.end()) st.erase({dist[sus][lo][hi], sus});
                dist[sus][lo][hi] = len + 1;
                st.insert({dist[sus][lo][hi], sus});
            }
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> w >> h;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
            if ('1' <= a[i][j] && a[i][j] <= '9') {
                robot[a[i][j] - '1'] = i*w+j;
            }
        }
    }
    build_succesor();
    build_graph();
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            solve(i, i + len - 1);
        }
    }
    for (auto x : v) sol = min(sol, dist[x][0][n - 1]);
    if (sol == 1e9) cout << -1; else cout << sol;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 6 ms 4352 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 6 ms 4352 KB Output is correct
5 Correct 6 ms 4352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 6 ms 4352 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 6 ms 4352 KB Output is correct
5 Correct 6 ms 4352 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 7 ms 4352 KB Output is correct
8 Correct 6 ms 4352 KB Output is correct
9 Correct 7 ms 4352 KB Output is correct
10 Correct 7 ms 4352 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 6 ms 4352 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 6 ms 4352 KB Output is correct
5 Correct 6 ms 4352 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 7 ms 4352 KB Output is correct
8 Correct 6 ms 4352 KB Output is correct
9 Correct 7 ms 4352 KB Output is correct
10 Correct 7 ms 4352 KB Output is correct
11 Correct 274 ms 31864 KB Output is correct
12 Correct 27 ms 30592 KB Output is correct
13 Correct 17 ms 7680 KB Output is correct
14 Correct 1056 ms 32888 KB Output is correct
15 Correct 156 ms 31096 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 6 ms 4352 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 6 ms 4352 KB Output is correct
5 Correct 6 ms 4352 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 7 ms 4352 KB Output is correct
8 Correct 6 ms 4352 KB Output is correct
9 Correct 7 ms 4352 KB Output is correct
10 Correct 7 ms 4352 KB Output is correct
11 Correct 274 ms 31864 KB Output is correct
12 Correct 27 ms 30592 KB Output is correct
13 Correct 17 ms 7680 KB Output is correct
14 Correct 1056 ms 32888 KB Output is correct
15 Correct 156 ms 31096 KB Output is correct
16 Correct 26 ms 15608 KB Output is correct
17 Execution timed out 1583 ms 84084 KB Time limit exceeded
18 Halted 0 ms 0 KB -