oj.uz

Submission #41152

# Submission time Handle Problem Language Result Execution time Memory
41152 2018-02-13T06:52:12 Z 14kg Portals (BOI14_portals) C++11
31 / 100
 61 ms 50996 KB 
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#define N 1001
#define INF 1000000000

using namespace std;
typedef pair<int,pair<int,int> > pip;
int n, m, board[N][N], go[N][N], d[N][N];
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
bool go_check[N][N], check[N][N];
pair<int,int> S, E;
vector<pair<int,int> > p[N][N], O[1000001];
queue<int> Q;
queue<pip> PQ;

void bfs_go(){
    int ty, tx, yy, xx;
    bool w_check;

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++){
            w_check=false;
            for(int s=0; s<4; s++){
                ty=i+dy[s], tx=j+dx[s];
                if(ty<1 || ty>n || tx<1 || tx>m) w_check=true;
                else if(board[ty][tx]) w_check=true;
            }
            if(w_check){
                go_check[i][j]=true, Q.push(i), Q.push(j);
            }
        }

    while(!Q.empty()){
        yy=Q.front(), Q.pop();
        xx=Q.front(), Q.pop();

        for(int i=0; i<4; i++){
            ty=yy+dy[i], tx=xx+dx[i];
            if(1<=ty && ty<=n && 1<=tx && tx<=m && go_check[ty][tx]==false && board[ty][tx]==0){
                go[ty][tx]=go[yy][xx]+1, go_check[ty][tx]=true;
                Q.push(ty), Q.push(tx);
            }
        }
    }
}
void Push(){
    pair<int,int> temp;

    for(int i=1; i<=n; i++){
        temp={i,1};
        for(int j=1; j<=m; j++){
            if(board[i][j]) temp={i,j+1};
            else p[i][j].push_back(temp);
        }
    }
    for(int i=1; i<=n; i++){
        temp={i,m};
        for(int j=m; j>=1; j--){
            if(board[i][j]) temp={i,j-1};
            else p[i][j].push_back(temp);
        }
    }
    for(int j=1; j<=m; j++){
        temp={1,j};
        for(int i=1; i<=n; i++){
            if(board[i][j]) temp={i+1,j};
            else p[i][j].push_back(temp);
        }
    }
    for(int j=1; j<=m; j++){
        temp={n,j};
        for(int i=n; i>=1; i--){
            if(board[i][j]) temp={i-1,j};
            else p[i][j].push_back(temp);
        }
    }
}
void PQ_push(int yy, int xx){
    int ty, tx;

    if(check[yy][xx]) return;
    check[yy][xx]=true;

    for(int i=0; i<4; i++){
        ty=yy+dy[i], tx=xx+dx[i];
        if(1<=ty && ty<=n && 1<=tx && tx<=m && d[ty][tx]>d[yy][xx]+1 && board[ty][tx]==0){
            d[ty][tx]=d[yy][xx]+1;
            PQ.push({d[ty][tx],{ty,tx}});
        }
    }
    for(vector<pair<int,int> >::iterator it=p[yy][xx].begin(); it!=p[yy][xx].end(); it++){
        ty=it->first, tx=it->second;
        if(d[ty][tx]>d[yy][xx]+go[yy][xx]+1){
            d[ty][tx]=d[yy][xx]+go[yy][xx]+1;
            O[d[ty][tx]].push_back({ty,tx});
        }
    }
}
int main(){
    int O_path=0;
    char in[1005];

    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++){
        scanf("%s",in+1);
        for(int j=1; j<=m; j++)
            if(in[j]=='#') board[i][j]=1;
            else if(in[j]=='S') S={i,j};
            else if(in[j]=='C') E={i,j};
    }

    bfs_go(), Push();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) d[i][j]=INF;

    PQ.push({0,{S.first,S.second}}), d[S.first][S.second]=0;
    while(!PQ.empty()){
        int k=PQ.front().first;

        for(int i=O_path+1; i<=k; i++)
            for(vector<pair<int,int> >::iterator it=O[k].begin(); it!=O[k].end(); it++){
                PQ_push(it->first,it->second);
            }
        O_path=k;

        while(PQ.empty()==false && PQ.front().first==k){
            PQ_push(PQ.front().second.first,PQ.front().second.second), PQ.pop();
        }
    }
    printf("%d",d[E.first][E.second]);
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:105:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
                         ^
portals.cpp:107:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",in+1);
                         ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47480 KB Output is correct
2 Correct 40 ms 47584 KB Output is correct
3 Correct 40 ms 47584 KB Output is correct
4 Correct 39 ms 47584 KB Output is correct
5 Correct 40 ms 47688 KB Output is correct
6 Correct 43 ms 47752 KB Output is correct
7 Correct 40 ms 47752 KB Output is correct
8 Correct 42 ms 47752 KB Output is correct
9 Correct 40 ms 47752 KB Output is correct
10 Correct 40 ms 47752 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47752 KB Output is correct
2 Correct 44 ms 47752 KB Output is correct
3 Correct 43 ms 47752 KB Output is correct
4 Correct 39 ms 47752 KB Output is correct
5 Correct 41 ms 47752 KB Output is correct
6 Correct 41 ms 47752 KB Output is correct
7 Correct 43 ms 47752 KB Output is correct
8 Correct 41 ms 47752 KB Output is correct
9 Correct 42 ms 48492 KB Output is correct
10 Correct 40 ms 48492 KB Output is correct
11 Incorrect 42 ms 48492 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 48492 KB Output is correct
2 Correct 40 ms 48492 KB Output is correct
3 Correct 41 ms 48492 KB Output is correct
4 Correct 42 ms 48492 KB Output is correct
5 Correct 54 ms 50796 KB Output is correct
6 Correct 53 ms 50924 KB Output is correct
7 Correct 61 ms 50996 KB Output is correct
8 Correct 54 ms 50996 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 50996 KB Output is correct
2 Correct 40 ms 50996 KB Output is correct
3 Correct 50 ms 50996 KB Output is correct
4 Correct 40 ms 50996 KB Output is correct
5 Correct 40 ms 50996 KB Output is correct
6 Correct 41 ms 50996 KB Output is correct
7 Correct 40 ms 50996 KB Output is correct
8 Correct 38 ms 50996 KB Output is correct
9 Correct 42 ms 50996 KB Output is correct
10 Correct 41 ms 50996 KB Output is correct
11 Incorrect 38 ms 50996 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 50996 KB Output is correct
2 Correct 37 ms 50996 KB Output is correct
3 Correct 40 ms 50996 KB Output is correct
4 Correct 41 ms 50996 KB Output is correct
5 Correct 47 ms 50996 KB Output is correct
6 Correct 38 ms 50996 KB Output is correct
7 Correct 39 ms 50996 KB Output is correct
8 Correct 39 ms 50996 KB Output is correct
9 Correct 48 ms 50996 KB Output is correct
10 Correct 39 ms 50996 KB Output is correct
11 Incorrect 41 ms 50996 KB Output isn't correct
12 Halted 0 ms 0 KB -