oj.uz

Submission #376550

# Submission time Handle Problem Language Result Execution time Memory
376550 2021-03-11T16:56:56 Z astoria Dango Maker (JOI18_dango_maker) C++14
0 / 100
 140 ms 262148 KB 
#include "bits/stdc++.h"
using namespace std;

#define int short

const int N=3005,M=3005;
vector<pair<pair<int,int>,int> > g[N][M][2]; //j=0,i=1;
bool is[N][M][2];
bool vis[N][M][2];

pair<int,int> dfs(int x, int y, int k){
	if(vis[x][y][k]) return {0,0};
	vis[x][y][k] = 1;
	pair<int,int> an;
	if(k==0) an={1,0};
	else an={0,1};
	for(auto ii : g[x][y][k]){
		pair<int,int> their = dfs(ii.first.first,ii.first.second,ii.second);
		an.first += their.first; an.second += their.second;
	}
	return an;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	char grid[n+5][m+5];
	
	for(int i=0; i<=n+1; i++){
		for(int j=0; j<=m+1; j++){
			grid[i][j]='p';
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin>>grid[i][j];
		}
	}
	
	
	memset(is,0,sizeof(is));
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(grid[i][j]!='G') continue;
			
			if(grid[i][j-1]=='R'&&grid[i][j+1]=='W'){
				is[i][j][0]=1;
			}
			if(grid[i-1][j]=='R'&&grid[i+1][j]=='W'){
				is[i][j][1]=1;
			}
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(!is[i][j][0]) continue;
			if(is[i][j][1]){
				g[i][j][0].push_back({{i,j},1});
			}
			if(is[i-1][j+1][1]){
				g[i][j][0].push_back({{i-1,j+1},1});
			}
			if(is[i+1][j-1][1]){
				g[i][j][0].push_back({{i+1,j-1},1});
			}
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(!is[i][j][1]) continue;
			if(is[i][j][0]){
				g[i][j][1].push_back({{i,j},0});
			}
			if(is[i-1][j+1][0]){
				g[i][j][1].push_back({{i-1,j+1},0});
			}
			if(is[i+1][j-1][0]){
				g[i][j][1].push_back({{i+1,j-1},0});
			}
		}
	}
	//cout<<"HEY"<<endl;
	memset(vis,0,sizeof(vis));
	int tot=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(is[i][j][0]&&!vis[i][j][0]){
				pair<int,int> an = dfs(i,j,0);
				tot += max(an.first,an.second);
			}
			if(is[i][j][1]&&!vis[i][j][1]){
				pair<int,int> an = dfs(i,j,1);
				tot += max(an.first,an.second);
			}
		}
	}
	
	cout<<tot;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -