Submission #855077

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
855077	2023-09-30T05:02:07 Z	prof_x	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1433 ms	96544 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	23 ms	12892 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	4700 KB	Output is correct
4	Correct	13 ms	13148 KB	Output is correct
5	Correct	7 ms	8796 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	4696 KB	Output is correct
8	Correct	1 ms	6748 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	4 ms	8796 KB	Output is correct
11	Correct	4 ms	8792 KB	Output is correct
12	Correct	9 ms	8816 KB	Output is correct
13	Correct	5 ms	8796 KB	Output is correct
14	Correct	5 ms	8796 KB	Output is correct
15	Correct	20 ms	12912 KB	Output is correct
16	Correct	32 ms	12920 KB	Output is correct
17	Correct	16 ms	12924 KB	Output is correct
18	Correct	13 ms	13148 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	76380 KB	Output is correct
2	Correct	97 ms	29348 KB	Output is correct
3	Correct	683 ms	78672 KB	Output is correct
4	Correct	159 ms	39556 KB	Output is correct
5	Correct	382 ms	62068 KB	Output is correct
6	Correct	1433 ms	96544 KB	Output is correct
7	Correct	10 ms	78424 KB	Output is correct
8	Correct	12 ms	76448 KB	Output is correct
9	Correct	6 ms	2396 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	10 ms	78568 KB	Output is correct
12	Correct	2 ms	6744 KB	Output is correct
13	Correct	86 ms	29352 KB	Output is correct
14	Correct	49 ms	21076 KB	Output is correct
15	Correct	58 ms	23124 KB	Output is correct
16	Correct	42 ms	10840 KB	Output is correct
17	Correct	224 ms	41684 KB	Output is correct
18	Correct	182 ms	41844 KB	Output is correct
19	Correct	158 ms	39508 KB	Output is correct
20	Correct	169 ms	37480 KB	Output is correct
21	Correct	394 ms	64180 KB	Output is correct
22	Correct	379 ms	62156 KB	Output is correct
23	Correct	424 ms	52188 KB	Output is correct
24	Correct	375 ms	64084 KB	Output is correct
25	Correct	819 ms	78932 KB	Output is correct
26	Correct	712 ms	72524 KB	Output is correct
27	Correct	1002 ms	82072 KB	Output is correct
28	Correct	1364 ms	96360 KB	Output is correct
29	Correct	1311 ms	92576 KB	Output is correct
30	Correct	1204 ms	92112 KB	Output is correct
31	Correct	956 ms	69180 KB	Output is correct
32	Correct	864 ms	80896 KB	Output is correct