oj.uz

Submission #101538

# Submission time Handle Problem Language Result Execution time Memory
101538 2019-03-19T03:51:10 Z rainy Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 2000 ms 1049600 KB 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
#define INF 1000000000
using namespace std;
typedef vector<short> vi;
typedef pair<int,int>ii;
int H,W;
char X;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

void prvt(vector<vi> vv){
    printf("---\n");
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(vv[i][j]==-1)printf("-");
            else printf("%hd",vv[i][j]);
        }
        printf("\n");
    }
    printf("---\n");
}

int tis(vector<vi> x, int ani){
    queue<ii>q;q.push(ii(0,0));
    x[0][0]=-1;
    bool vis[H+5][W+5]={false};
    vis[0][0]=true;
    while(!q.empty()){
        int x1=q.front().first,y1=q.front().second;
        q.pop();
        for(int k=0;k<4;k++){
            int nx=x1+dx[k],ny=y1+dy[k];
            if(0<=nx&&nx<H&&0<=ny&&ny<W){
                if(!vis[nx][ny]){
                    if(x[nx][ny]==-1||x[nx][ny]==ani){
                        vis[nx][ny]=true;
                        x[nx][ny]=-1;
                        q.push(ii(nx,ny));
                    }
                }
            }
        }
    }
    //prvt(x);
    if(!vis[H-1][W-1])return INF;
    bool isDone=true;bool has1=false,has2=false;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(x[i][j]==1){
                has1=true;isDone=false;
            }
            if(x[i][j]==2){
                has2=true;isDone=false;
            }
        }
    }
    if(isDone)return 0;
    return 1+min(tis(x,1),tis(x,2));
}

int main(){
    scanf("%d%d",&H,&W);
    vector<vi> gr(H);
    for(int i=0;i<H;i++){
        vi xyz(W);
        for(int j=0;j<W;j++){
            xyz[j]=-1;
        }
        gr[i]=xyz;
    }
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            scanf(" %c",&X);
            if(X=='.')gr[i][j]=0;
            if(X=='F')gr[i][j]=1;
            if(X=='R')gr[i][j]=2;
        }
    }
    /*
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            printf("%d",gr[i][j]);
        }
        printf("\n");
    }
    */
    printf("%d\n",1+tis(gr,gr[0][0]));
    return 0;
}

Compilation message

tracks.cpp: In function 'int tis(std::vector<std::vector<short int> >, int)':
tracks.cpp:50:27: warning: variable 'has1' set but not used [-Wunused-but-set-variable]
     bool isDone=true;bool has1=false,has2=false;
                           ^~~~
tracks.cpp:50:38: warning: variable 'has2' set but not used [-Wunused-but-set-variable]
     bool isDone=true;bool has1=false,has2=false;
                                      ^~~~
tracks.cpp: In function 'int main()':
tracks.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&H,&W);
     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",&X);
             ~~~~~^~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2122 ms 1043768 KB Time limit exceeded
2 Runtime error 1623 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Execution timed out 2123 ms 924664 KB Time limit exceeded
4 Execution timed out 2050 ms 254860 KB Time limit exceeded
5 Runtime error 1484 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 1669 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Execution timed out 2143 ms 903708 KB Time limit exceeded
8 Execution timed out 2068 ms 315764 KB Time limit exceeded
9 Runtime error 1598 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 1337 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Execution timed out 2066 ms 277720 KB Time limit exceeded
12 Runtime error 1732 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 1535 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 1452 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 1720 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Execution timed out 2095 ms 1049600 KB Time limit exceeded
17 Runtime error 1513 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Execution timed out 2033 ms 263760 KB Time limit exceeded

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 1885 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 1606 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Execution timed out 2153 ms 878068 KB Time limit exceeded
4 Runtime error 1647 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Execution timed out 2040 ms 1049600 KB Time limit exceeded
6 Execution timed out 2111 ms 318552 KB Time limit exceeded
7 Runtime error 1839 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 1702 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Execution timed out 2111 ms 788780 KB Time limit exceeded
10 Execution timed out 2036 ms 1049600 KB Time limit exceeded
11 Execution timed out 2037 ms 1049600 KB Time limit exceeded
12 Runtime error 1598 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 1443 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 1307 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 1362 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 1513 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 1637 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 1549 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 1608 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 1531 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 1846 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 1954 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Execution timed out 2109 ms 1045476 KB Time limit exceeded
24 Execution timed out 2123 ms 1023936 KB Time limit exceeded
25 Execution timed out 2156 ms 769012 KB Time limit exceeded
26 Correct 1560 ms 63608 KB Output is correct
27 Execution timed out 2037 ms 128692 KB Time limit exceeded
28 Execution timed out 2052 ms 270176 KB Time limit exceeded
29 Execution timed out 2032 ms 270168 KB Time limit exceeded
30 Execution timed out 2029 ms 126040 KB Time limit exceeded
31 Execution timed out 2086 ms 927656 KB Time limit exceeded
32 Execution timed out 2108 ms 1024388 KB Time limit exceeded