Submission #503894

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
503894	2022-01-09T06:37:19 Z	zwicky	Tracks in the Snow (BOI13_tracks)	C++14	14.2708 / 100	2000 ms	1048580 KB

tracks

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define nl endl
#define loop(i,a,b) for(ll i=a;i<b;i++) 
#define rloop(i,a,b) for(ll i=b;i>=a;i--)
#define cy cout<<"YES"<<endl;
#define cn cout<<"NO"<<endl;
#define cm cout<<-1<<endl
#define vl vector<ll>
#define vchar vector<char>
#define vvll vector<vector<ll>>
#define vvcr vector<vchar>
#define deb(x) cout<<#x<<" "<<x<<endl;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
using namespace std;

const ll MOD=1e9+7;

ll binepow(ll a,ll b,ll mod=-1){
	if(b==0){
		return 1ll;
	}
	if(mod!=-1){
		ll k=binepow(a,b/2,mod);
		if(b%2==0){
			return (k*k)%mod;
		}
		else{
			return (((k*a)%mod)*k)%mod;
		}
	}
	else{
		ll k=binepow(a,b/2,mod);
		if(b%2==0){
			return (k*k);
		}
		else{
			return k*k*a;
		}
	}
}

////////////////////////////////////////////////////////

void solve(){
	ll n,m;
	cin>>n>>m;
	vvcr a(n,vchar(m,'.'));
	ll total=0;
	loop(i,0,n){
		loop(j,0,m){
			cin>>a[i][j];
			if(a[i][j]!='.'){
				total++;
			}
		}
	}
	ll ans=0;
	char role=a[0][0];
	while (total!=0)
	{
		vvll vis(n,vl(m,0));
		queue<pair<ll,ll>> q;
		q.push({0,0});
		vis[0][0]=1;
		while (q.size()!=0)
		{
			if(a[q.front().first][q.front().second]==role){
				a[q.front().first][q.front().second]='x';
				total--;
			}
			ll x=q.front().first,y=q.front().second;
			vis[x][y]=1;
			if(x>0 && (a[x-1][y]==role || a[x-1][y]=='x' ) && vis[x-1][y]==0){
				q.push({x-1,y});
			}
			if(y>0 && (a[x][y-1]==role || a[x][y-1]=='x' ) && vis[x][y-1]==0){
				q.push({x,y-1});
			}
			if(x<n-1 && (a[x+1][y]==role || a[x+1][y]=='x' ) && vis[x+1][y]==0){
				q.push({x+1,y});
			}
			if(y<m-1 && (a[x][y+1]==role || a[x][y+1]=='x' ) && vis[x][y+1]==0){
				q.push({x,y+1});
			}
			q.pop();
		}
		ans++;
		if(role=='R'){
			role='F';
		}
		else{
			role='R';
		}
	}
	cout<<ans<<nl;
	return;
}

int main(){
   ios::sync_with_stdio(0);
   cin.tie(0);
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
	// ll t;
	// cin>>t;
	// while(t--){
	// 	solve();
	// }
	solve();
}

Subtask #1

3.33333333333 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2111 ms	688808 KB	Time limit exceeded
2	Correct	1 ms	204 KB	Output is correct
3	Execution timed out	2127 ms	890324 KB	Time limit exceeded
4	Execution timed out	2108 ms	672188 KB	Time limit exceeded
5	Execution timed out	2051 ms	365756 KB	Time limit exceeded
6	Correct	1 ms	308 KB	Output is correct
7	Execution timed out	2152 ms	938084 KB	Time limit exceeded
8	Execution timed out	2120 ms	562836 KB	Time limit exceeded
9	Execution timed out	2060 ms	27776 KB	Time limit exceeded
10	Execution timed out	2067 ms	659392 KB	Time limit exceeded
11	Execution timed out	2086 ms	1048580 KB	Time limit exceeded
12	Execution timed out	2051 ms	392396 KB	Time limit exceeded
13	Execution timed out	2098 ms	314612 KB	Time limit exceeded
14	Execution timed out	2101 ms	358912 KB	Time limit exceeded
15	Execution timed out	2037 ms	339848 KB	Time limit exceeded
16	Execution timed out	2041 ms	636024 KB	Time limit exceeded
17	Execution timed out	2120 ms	590032 KB	Time limit exceeded
18	Execution timed out	2088 ms	656672 KB	Time limit exceeded

Subtask #2

10.9375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2051 ms	972 KB	Time limit exceeded
2	Execution timed out	2059 ms	261336 KB	Time limit exceeded
3	Execution timed out	2082 ms	162392 KB	Time limit exceeded
4	Execution timed out	2036 ms	192840 KB	Time limit exceeded
5	Execution timed out	2029 ms	89052 KB	Time limit exceeded
6	Execution timed out	2032 ms	397876 KB	Time limit exceeded
7	Correct	1517 ms	1024 KB	Output is correct
8	Correct	1978 ms	1068 KB	Output is correct
9	Execution timed out	2079 ms	27772 KB	Time limit exceeded
10	Correct	502 ms	820 KB	Output is correct
11	Correct	973 ms	1080 KB	Output is correct
12	Correct	1759 ms	720 KB	Output is correct
13	Execution timed out	2090 ms	321992 KB	Time limit exceeded
14	Execution timed out	2067 ms	314024 KB	Time limit exceeded
15	Execution timed out	2071 ms	10648 KB	Time limit exceeded
16	Execution timed out	2045 ms	216408 KB	Time limit exceeded
17	Execution timed out	2099 ms	255764 KB	Time limit exceeded
18	Execution timed out	2087 ms	39904 KB	Time limit exceeded
19	Execution timed out	2071 ms	192800 KB	Time limit exceeded
20	Execution timed out	2082 ms	34624 KB	Time limit exceeded
21	Execution timed out	2005 ms	92056 KB	Time limit exceeded
22	Execution timed out	2090 ms	88948 KB	Time limit exceeded
23	Execution timed out	2049 ms	240680 KB	Time limit exceeded
24	Execution timed out	2102 ms	89768 KB	Time limit exceeded
25	Execution timed out	2088 ms	157416 KB	Time limit exceeded
26	Execution timed out	2040 ms	1048580 KB	Time limit exceeded
27	Execution timed out	2104 ms	1007728 KB	Time limit exceeded
28	Execution timed out	2070 ms	398140 KB	Time limit exceeded
29	Execution timed out	2100 ms	1048580 KB	Time limit exceeded
30	Execution timed out	2058 ms	503580 KB	Time limit exceeded
31	Execution timed out	2016 ms	294428 KB	Time limit exceeded
32	Execution timed out	2056 ms	162056 KB	Time limit exceeded