oj.uz

답안 #503894

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503894 2022-01-09T06:37:19 Z zwicky Tracks in the Snow (BOI13_tracks) C++14
14.2708 / 100
 2000 ms 1048580 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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