Submission #855076

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
855076	2023-09-30T05:01:56 Z	prof_x	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1411 ms	112140 KB

tracks

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
const int MAXN=4000+5;
int  g[MAXN][MAXN];
bool visited[MAXN][MAXN];

void solve()
{
  int h,k;

  cin>>h>>k;


  for(int i =0;i<=h;i++)
  {
    for(int j=0;j<=k;j++)
    {
      visited[i][j]=false;
      
    }
  }
  for(int i=1;i<=h;i++)
  {
    for(int j=1;j<=k;j++)
    {
      char ch;
      cin>>ch;
      
      switch(ch)
      {
        case 'F':g[i][j]=1;break;
        case '.':visited[i][j]=true;break;
        case 'R':g[i][j]=0;break;
        
      }
    }
  }

  queue<pair<int,int>>q[2];
  int ans=0;
  int kiss=0;
  q[0].push({1,1});
  q[0].push({h,k});
  while(!q[kiss].empty())
  {
    while(!q[kiss].empty())
    {
      int x=q[kiss].front().first;
      int y=q[kiss].front().second;
      q[kiss].pop();
      
      if(visited[x][y])continue;
      visited[x][y]=true;
      for(int i=0;i<4;i++)
      {
        int fx=x+dx[i];
        int fy=y+dy[i];
        if(fx<1||fx>h||fy<1||fy>k||visited[fx][fy])continue;
        if(g[x][y]^g[fx][fy])q[1-kiss].push({fx,fy});
        else
        q[kiss].push({fx,fy});      
        
      }
    }
    kiss^=1;
    ans++;
    
  }
  cout<<ans<<endl;
  
}



int main()
{
  int t;
  t=1;
  solve();
  return 0;
  
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:79:7: warning: variable 't' set but not used [-Wunused-but-set-variable]
   79 |   int t;
      |       ^

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	13148 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	4700 KB	Output is correct
4	Correct	15 ms	13072 KB	Output is correct
5	Correct	5 ms	8796 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	4700 KB	Output is correct
8	Correct	1 ms	6748 KB	Output is correct
9	Correct	2 ms	6748 KB	Output is correct
10	Correct	5 ms	8796 KB	Output is correct
11	Correct	4 ms	8796 KB	Output is correct
12	Correct	9 ms	8980 KB	Output is correct
13	Correct	5 ms	8796 KB	Output is correct
14	Correct	5 ms	8796 KB	Output is correct
15	Correct	23 ms	13148 KB	Output is correct
16	Correct	25 ms	13464 KB	Output is correct
17	Correct	15 ms	13144 KB	Output is correct
18	Correct	13 ms	13300 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	76484 KB	Output is correct
2	Correct	87 ms	30688 KB	Output is correct
3	Correct	686 ms	94512 KB	Output is correct
4	Correct	160 ms	43396 KB	Output is correct
5	Correct	366 ms	70996 KB	Output is correct
6	Correct	1350 ms	112140 KB	Output is correct
7	Correct	11 ms	78684 KB	Output is correct
8	Correct	11 ms	76380 KB	Output is correct
9	Correct	4 ms	2652 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	11 ms	78684 KB	Output is correct
12	Correct	2 ms	6748 KB	Output is correct
13	Correct	102 ms	30828 KB	Output is correct
14	Correct	53 ms	21980 KB	Output is correct
15	Correct	46 ms	24148 KB	Output is correct
16	Correct	40 ms	11516 KB	Output is correct
17	Correct	228 ms	45556 KB	Output is correct
18	Correct	179 ms	45416 KB	Output is correct
19	Correct	158 ms	43256 KB	Output is correct
20	Correct	157 ms	41068 KB	Output is correct
21	Correct	394 ms	73300 KB	Output is correct
22	Correct	366 ms	71248 KB	Output is correct
23	Correct	417 ms	59476 KB	Output is correct
24	Correct	387 ms	73244 KB	Output is correct
25	Correct	832 ms	94548 KB	Output is correct
26	Correct	762 ms	84572 KB	Output is correct
27	Correct	1115 ms	97916 KB	Output is correct
28	Correct	1411 ms	111944 KB	Output is correct
29	Correct	1383 ms	108384 KB	Output is correct
30	Correct	1252 ms	107184 KB	Output is correct
31	Correct	989 ms	78992 KB	Output is correct
32	Correct	919 ms	96532 KB	Output is correct