oj.uz

Submission #206801

# Submission time Handle Problem Language Result Execution time Memory
206801 2020-03-05T12:30:24 Z MvC Tracks in the Snow (BOI13_tracks) C++11
100 / 100
 1383 ms 115440 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=4e3+50;
const int mod=1e9+7;
using namespace std;
int n,m,i,j,rs,ix,jx,viz[nmax][nmax],t,di[5],dj[5];
char c[nmax][nmax],cur;
queue<pair<int,int> >q,q1;
bool ok(int x,int y)
{
	if(x<1 || x>n || y<1 || y>m || viz[x][y] || c[x][y]=='.')return 0;
	return 1;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	di[0]=-1,di[1]=1,dj[2]=-1,dj[3]=1;
	cin>>n>>m;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)cin>>c[i][j];
	cur=c[1][1];
	viz[1][1]=1;
	q.push(mkp(1,1));
	for(rs=1;;rs++)
	{
		while(!q.empty())
		{
			i=q.front().fr,j=q.front().sc;
			q.pop();
			for(t=0;t<4;t++)
			{
				ix=i+di[t],jx=j+dj[t];
				if(!ok(ix,jx))continue;
				viz[ix][jx]=1;
				if(c[ix][jx]==cur)q.push(mkp(ix,jx));
				else q1.push(mkp(ix,jx));
			}
		}
		if(q1.empty())break;
		q=q1;
		while(!q1.empty())q1.pop();
		if(cur=='F')cur='R';
		else cur='F';
	}
	cout<<rs<<endl;
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5496 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 15 ms 5232 KB Output is correct
5 Correct 9 ms 3064 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 5 ms 888 KB Output is correct
9 Correct 5 ms 1148 KB Output is correct
10 Correct 9 ms 2552 KB Output is correct
11 Correct 8 ms 2172 KB Output is correct
12 Correct 11 ms 3196 KB Output is correct
13 Correct 9 ms 3068 KB Output is correct
14 Correct 9 ms 3064 KB Output is correct
15 Correct 21 ms 5368 KB Output is correct
16 Correct 22 ms 5500 KB Output is correct
17 Correct 19 ms 5244 KB Output is correct
18 Correct 15 ms 5360 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 30968 KB Output is correct
2 Correct 85 ms 15096 KB Output is correct
3 Correct 445 ms 74104 KB Output is correct
4 Correct 132 ms 32888 KB Output is correct
5 Correct 410 ms 53824 KB Output is correct
6 Correct 1383 ms 115440 KB Output is correct
7 Correct 22 ms 32504 KB Output is correct
8 Correct 24 ms 31096 KB Output is correct
9 Correct 7 ms 760 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 27 ms 31864 KB Output is correct
12 Correct 7 ms 1656 KB Output is correct
13 Correct 91 ms 15224 KB Output is correct
14 Correct 48 ms 10616 KB Output is correct
15 Correct 45 ms 13288 KB Output is correct
16 Correct 39 ms 5756 KB Output is correct
17 Correct 225 ms 29048 KB Output is correct
18 Correct 162 ms 35832 KB Output is correct
19 Correct 132 ms 32888 KB Output is correct
20 Correct 106 ms 25852 KB Output is correct
21 Correct 266 ms 52860 KB Output is correct
22 Correct 409 ms 53752 KB Output is correct
23 Correct 424 ms 43896 KB Output is correct
24 Correct 310 ms 50040 KB Output is correct
25 Correct 688 ms 95500 KB Output is correct
26 Correct 796 ms 81756 KB Output is correct
27 Correct 1031 ms 98168 KB Output is correct
28 Correct 1302 ms 115300 KB Output is correct
29 Correct 1288 ms 111308 KB Output is correct
30 Correct 1083 ms 105760 KB Output is correct
31 Correct 994 ms 74612 KB Output is correct
32 Correct 854 ms 96328 KB Output is correct