oj.uz

Submission #580896

# Submission time Handle Problem Language Result Execution time Memory
580896 2022-06-22T05:31:54 Z 반딧불(#8360) Robots (APIO13_robots) C++17
100 / 100
 459 ms 55876 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int xx[]={0, -1, 0, 1}, yy[]={1, 0, -1, 0};

int n, m, k;
char board[502][502];
int sx[10], sy[10];

void input();
void operate();
void output();

int main(){
    input();
    operate();
    output();
}

void input(){
    scanf("%d %d %d", &k, &m, &n);
    for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++) board[i][j] = 'x';
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        scanf(" %c", &board[i][j]);
        if(isdigit(board[i][j])){
            int tmp = board[i][j] - '0';
            sx[tmp] = i, sy[tmp] = j;
            board[i][j] = '.';
        }
    }
}

int endpointX[502][502][4];
int endpointY[502][502][4];

void calculateEndpoints(){
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) for(int d=0; d<4; d++) endpointX[i][j][d] = -1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(board[i][j]=='x') continue;
            for(int d=0; d<4; d++){
                if(board[i+xx[d]][j+yy[d]]!='x') continue;
                int x=i, y=j, td=d;
                while(board[x][y]!='x'){
                    if(board[x][y]=='A') td=(td+3)%4;
                    if(board[x][y]=='C') td=(td+1)%4;
                    endpointX[x][y][td] = i;
                    endpointY[x][y][td] = j;
                    x-=xx[td], y-=yy[td];
                }
            }
        }
    }
}

int DP[10][10][502][502];

void init(){
    for(int l=1; l<=k; l++) for(int r=l; r<=k; r++) for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        DP[l][r][i][j] = 1e9;
    }
    for(int i=1; i<=k; i++){
        DP[i][i][sx[i]][sy[i]] = 0;
    }
}

struct dat{
    int x, y, d;
    dat(){}
    dat(int x, int y, int d): x(x), y(y), d(d){}
    bool operator<(const dat &r)const{
        return d>r.d;
    }
};
bool visited[502][502];

void calculateDP(int l, int r){
    memset(visited, 0, sizeof(visited));
    vector<dat> vec;
    queue<dat> que;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(DP[l][r][i][j] >= 1e9) continue;
            vec.push_back(dat(i, j, DP[l][r][i][j]));
        }
    }
    sort(vec.rbegin(), vec.rend());
    int pnt = 0;

    while(!que.empty() || pnt < (int)vec.size()){
        if(que.empty()){
            que.push(vec[pnt++]);
        }
        dat tmp;
        if(pnt < (int)vec.size() && vec[pnt].d <= que.front().d) tmp = vec[pnt++];
        else tmp = que.front(), que.pop();

        int x = tmp.x, y = tmp.y, d = tmp.d;
//        printf("%d %d %d\n", x, y, d);
        if(d>=1e9 || visited[x][y]) continue;
        DP[l][r][x][y] = d;
        visited[x][y] = 1;
        for(int c=0; c<4; c++){
            if(endpointX[x][y][c] == -1) continue;
            if(visited[endpointX[x][y][c]][endpointY[x][y][c]]) continue;
            que.push(dat(endpointX[x][y][c], endpointY[x][y][c], d+1));
        }
    }
}

void operate(){
    calculateEndpoints();
    init();
    for(int d=0; d<k; d++){
        for(int i=1; i+d<=k; i++){
            int j = i+d;
            for(int mid=i; mid<j; mid++){
                for(int x=1; x<=n; x++){
                    for(int y=1; y<=m; y++){
                        DP[i][j][x][y] = min(DP[i][j][x][y], DP[i][mid][x][y] + DP[mid+1][j][x][y]);
                    }
                }
            }
            calculateDP(i, j);
        }
    }

    #ifdef TEST
    for(int i=1; i<=k; i++) for(int j=i; j<=k; j++){
        printf("Matrix %d %d:\n", i, j);
        for(int x=1; x<=n; x++){
            for(int y=1; y<=m; y++){
                printf("%3d ", DP[i][j][x][y]>100?100:DP[i][j][x][y]);
            }
            puts("");
        }
    }
    #endif
}

void output(){
    int ans = INT_MAX;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) ans = min(ans, DP[1][k][i][j]);
    if(ans >= 1e9) printf("-1");
    else printf("%d", ans);
}

Compilation message

robots.cpp: In function 'void input()':
robots.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d %d", &k, &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf(" %c", &board[i][j]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 79 ms 32388 KB Output is correct
12 Correct 8 ms 5744 KB Output is correct
13 Correct 28 ms 21972 KB Output is correct
14 Correct 187 ms 33004 KB Output is correct
15 Correct 61 ms 32100 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 79 ms 32388 KB Output is correct
12 Correct 8 ms 5744 KB Output is correct
13 Correct 28 ms 21972 KB Output is correct
14 Correct 187 ms 33004 KB Output is correct
15 Correct 61 ms 32100 KB Output is correct
16 Correct 110 ms 53080 KB Output is correct
17 Correct 459 ms 55876 KB Output is correct
18 Correct 152 ms 54836 KB Output is correct
19 Correct 109 ms 53348 KB Output is correct
20 Correct 300 ms 55728 KB Output is correct