# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
134027 | 2019-07-22T00:21:23 Z | ly20 | Tracks in the Snow (BOI13_tracks) | C++17 | 1740 ms | 163452 KB |
#include<bits/stdc++.h> using namespace std; const int MAXN=4123,INF=1123456789; int dist[MAXN][MAXN]; int tb[MAXN][MAXN]; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; int main() { int n,m; scanf("%d %d",&n,&m); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { char c; scanf(" %c",&c); if(c=='F') { tb[i][j]=0; } if(c=='R') { tb[i][j]=1; } if(c=='.') { tb[i][j]=-1; } dist[i][j]=INF; } } deque<pair<int,int> > fila; fila.push_back(make_pair(0,0)); dist[0][0]=1; while(!fila.empty()) { int curx=fila.front().first,cury=fila.front().second;fila.pop_front(); for(int i=0;i<4;i++) { int vizx=curx+dx[i],vizy=cury+dy[i]; if(vizx<0 || vizx>=n || vizy<0 || vizy>=m)continue; if(tb[vizx][vizy]==-1)continue; if(tb[vizx][vizy]==tb[curx][cury]) { if(dist[curx][cury]<dist[vizx][vizy]) { dist[vizx][vizy]=dist[curx][cury]; fila.push_front(make_pair(vizx,vizy)); } } else { if(dist[curx][cury]<dist[vizx][vizy]-1) { dist[vizx][vizy]=dist[curx][cury]+1; fila.push_back(make_pair(vizx,vizy)); } } } } int resp=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(tb[i][j]!=-1)resp=max(resp,dist[i][j]); } } printf("%d\n",resp); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 6140 KB | Output is correct |
2 | Correct | 2 ms | 504 KB | Output is correct |
3 | Correct | 2 ms | 760 KB | Output is correct |
4 | Correct | 20 ms | 5624 KB | Output is correct |
5 | Correct | 11 ms | 3324 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 3 ms | 760 KB | Output is correct |
8 | Correct | 3 ms | 888 KB | Output is correct |
9 | Correct | 3 ms | 1272 KB | Output is correct |
10 | Correct | 9 ms | 2808 KB | Output is correct |
11 | Correct | 7 ms | 2296 KB | Output is correct |
12 | Correct | 14 ms | 3468 KB | Output is correct |
13 | Correct | 10 ms | 3320 KB | Output is correct |
14 | Correct | 10 ms | 3320 KB | Output is correct |
15 | Correct | 32 ms | 6496 KB | Output is correct |
16 | Correct | 35 ms | 6264 KB | Output is correct |
17 | Correct | 29 ms | 6012 KB | Output is correct |
18 | Correct | 20 ms | 5624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 31480 KB | Output is correct |
2 | Correct | 154 ms | 22648 KB | Output is correct |
3 | Correct | 1187 ms | 129552 KB | Output is correct |
4 | Correct | 310 ms | 44852 KB | Output is correct |
5 | Correct | 675 ms | 94744 KB | Output is correct |
6 | Correct | 1686 ms | 142748 KB | Output is correct |
7 | Correct | 30 ms | 32888 KB | Output is correct |
8 | Correct | 29 ms | 31480 KB | Output is correct |
9 | Correct | 7 ms | 764 KB | Output is correct |
10 | Correct | 4 ms | 504 KB | Output is correct |
11 | Correct | 29 ms | 32304 KB | Output is correct |
12 | Correct | 5 ms | 1784 KB | Output is correct |
13 | Correct | 153 ms | 22628 KB | Output is correct |
14 | Correct | 92 ms | 14712 KB | Output is correct |
15 | Correct | 89 ms | 16120 KB | Output is correct |
16 | Correct | 67 ms | 8696 KB | Output is correct |
17 | Correct | 390 ms | 48292 KB | Output is correct |
18 | Correct | 339 ms | 47748 KB | Output is correct |
19 | Correct | 312 ms | 44804 KB | Output is correct |
20 | Correct | 271 ms | 41320 KB | Output is correct |
21 | Correct | 722 ms | 98104 KB | Output is correct |
22 | Correct | 676 ms | 94848 KB | Output is correct |
23 | Correct | 748 ms | 81044 KB | Output is correct |
24 | Correct | 683 ms | 96416 KB | Output is correct |
25 | Correct | 1432 ms | 129468 KB | Output is correct |
26 | Correct | 1350 ms | 163452 KB | Output is correct |
27 | Correct | 1490 ms | 147824 KB | Output is correct |
28 | Correct | 1740 ms | 142744 KB | Output is correct |
29 | Correct | 1670 ms | 140584 KB | Output is correct |
30 | Correct | 1617 ms | 144176 KB | Output is correct |
31 | Correct | 1357 ms | 104324 KB | Output is correct |
32 | Correct | 1543 ms | 146424 KB | Output is correct |