oj.uz

Submission #814462

# Submission time Handle Problem Language Result Execution time Memory
814462 2023-08-08T07:38:42 Z SteGG Dango Maker (JOI18_dango_maker) C++17
13 / 100
 115 ms 235452 KB 
#include <bits/stdc++.h>
#define int long long
#define VERTICAL 1
#define HORIZONTAL 2
#define NOT_DONE 1
#define DONE 2

using namespace std;

void open(){
	if(fopen("input.inp", "r")){
		freopen("input.inp", "r", stdin);
		//freopen("output.out", "w", stdout);
	}
}

const int maxn = 1e7;
int n, m;
char board[3001][3001];
vector<int> G[maxn];
int vertical_change[3001][3001], horizontal_change[3001][3001];
pair<int, int> vertical_parent[3001][3001], horizontal_parent[3001][3001];
bool vertical_check[3001][3001], horizontal_check[3001][3001];
int cnt;
int state[3001][3001];
bool check[maxn];

int bfs(int root){
	queue<pair<int, bool>> q;
	q.push({root, true});
	int total = 0;
	int cur = 0;
	while(!q.empty()){
		pair<int, int> first = q.front();
		q.pop();
		int u = first.first;
		if(check[u]) continue;
		check[u] = true;
		total++;
		cur += first.second;
		for(int v : G[u]){
			q.push({v, first.second ^ 1});
		}
	}

	return max(cur, total - cur);
}

void build(int x, int y, int direction){
	if(state[x][y]) return;
	state[x][y] = NOT_DONE;

	if(direction == VERTICAL){
		int cur_index = vertical_change[x][y];
		int new_index;
		if(x + 2 > n || board[x + 1][y] != 'G' || board[x + 2][y] != 'W') return;
		// To G:
		if(horizontal_parent[x + 1][y] != make_pair(0ll, 0ll)){
			pair<int, int> temp = horizontal_parent[x + 1][y];
			new_index = horizontal_change[temp.first][temp.second];
			if(state[temp.first][temp.second] != NOT_DONE){
				G[cur_index].push_back(new_index);
				G[new_index].push_back(cur_index);
				build(temp.first, temp.second, HORIZONTAL);
			}
		}

		// To W:
		if(horizontal_parent[x + 2][y] != make_pair(0ll, 0ll)){
			pair<int, int> temp = horizontal_parent[x + 2][y];
			new_index = horizontal_change[temp.first][temp.second];
			if(state[temp.first][temp.second] != NOT_DONE){
				G[cur_index].push_back(new_index);
				G[new_index].push_back(cur_index);
				build(temp.first, temp.second, HORIZONTAL);
			}
		}
	}else{
		int cur_index = horizontal_change[x][y];
		int new_index;
		if(y + 2 > m || board[x][y + 1] != 'G' || board[x][y + 2] != 'W') return;
		// To G:
		if(vertical_parent[x][y + 1] != make_pair(0ll, 0ll)){
			pair<int, int> temp = vertical_parent[x][y + 1];
			new_index = vertical_change[temp.first][temp.second];
			if(state[temp.first][temp.second] != NOT_DONE){
				G[cur_index].push_back(new_index);
				G[new_index].push_back(cur_index);
				build(temp.first, temp.second, VERTICAL);
			}
		}

		// To W:
		if(vertical_parent[x][y + 1] != make_pair(0ll, 0ll)){
			pair<int, int> temp = vertical_parent[x][y + 1];
			new_index = vertical_change[temp.first][temp.second];
			if(state[temp.first][temp.second] != NOT_DONE){
				G[cur_index].push_back(new_index);
				G[new_index].push_back(cur_index);
				build(temp.first, temp.second, VERTICAL);
			}
		}
	}
	state[x][y] = DONE;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	open();
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> board[i][j];
		}
	}

	cnt = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(board[i][j] == 'R'){
				vertical_parent[i][j] = make_pair(i, j);
				horizontal_parent[i][j] = make_pair(i, j);
				// horizontal:
				if(j + 2 <= m && board[i][j + 1] == 'G' && board[i][j + 2] == 'W'){
					horizontal_change[i][j] = ++cnt;
					horizontal_parent[i][j + 1] = horizontal_parent[i][j + 2] = horizontal_parent[i][j];
					horizontal_check[i][j] = true;
				}
				// vertical:
				if(i + 2 <= n && board[i + 1][j] == 'G' && board[i + 2][j] == 'W'){
					vertical_change[i][j] = ++cnt;
					vertical_parent[i + 1][j] = vertical_parent[i + 2][j] = vertical_parent[i][j];
					vertical_check[i][j] = true;
				}
			}
		}
	}

	if(cnt == 0){
		cout << 0 << endl;
		return 0;
	}

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(board[i][j] == 'R'){
				build(i, j, VERTICAL);
				build(i, j, HORIZONTAL);
				if(vertical_check[i][j] && horizontal_check[i][j]){
					G[vertical_change[i][j]].push_back(horizontal_change[i][j]);
					G[horizontal_change[i][j]].push_back(vertical_change[i][j]);
				}
			}
		}
	}

	int result = 0;
	for(int i = 1; i <= cnt; i++){
		if(!check[i]){
			result += bfs(i);
		}
	}

	cout << result << endl;

	return 0;
}

Compilation message

dango_maker.cpp: In function 'void open()':
dango_maker.cpp:12:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   freopen("input.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 235084 KB Output is correct
2 Correct 109 ms 235068 KB Output is correct
3 Correct 107 ms 235116 KB Output is correct
4 Correct 107 ms 235076 KB Output is correct
5 Correct 108 ms 235144 KB Output is correct
6 Correct 108 ms 235192 KB Output is correct
7 Correct 110 ms 235212 KB Output is correct
8 Correct 110 ms 235152 KB Output is correct
9 Correct 113 ms 235388 KB Output is correct
10 Correct 108 ms 235188 KB Output is correct
11 Correct 109 ms 235164 KB Output is correct
12 Correct 110 ms 235212 KB Output is correct
13 Correct 110 ms 235188 KB Output is correct
14 Correct 115 ms 235112 KB Output is correct
15 Correct 108 ms 235212 KB Output is correct
16 Correct 111 ms 235212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 235084 KB Output is correct
2 Correct 109 ms 235068 KB Output is correct
3 Correct 107 ms 235116 KB Output is correct
4 Correct 107 ms 235076 KB Output is correct
5 Correct 108 ms 235144 KB Output is correct
6 Correct 108 ms 235192 KB Output is correct
7 Correct 110 ms 235212 KB Output is correct
8 Correct 110 ms 235152 KB Output is correct
9 Correct 113 ms 235388 KB Output is correct
10 Correct 108 ms 235188 KB Output is correct
11 Correct 109 ms 235164 KB Output is correct
12 Correct 110 ms 235212 KB Output is correct
13 Correct 110 ms 235188 KB Output is correct
14 Correct 115 ms 235112 KB Output is correct
15 Correct 108 ms 235212 KB Output is correct
16 Correct 111 ms 235212 KB Output is correct
17 Correct 110 ms 235280 KB Output is correct
18 Correct 113 ms 235220 KB Output is correct
19 Correct 111 ms 235360 KB Output is correct
20 Correct 109 ms 235388 KB Output is correct
21 Correct 112 ms 235388 KB Output is correct
22 Correct 109 ms 235348 KB Output is correct
23 Correct 109 ms 235340 KB Output is correct
24 Correct 111 ms 235300 KB Output is correct
25 Correct 109 ms 235212 KB Output is correct
26 Correct 109 ms 235112 KB Output is correct
27 Incorrect 114 ms 235452 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 235084 KB Output is correct
2 Correct 109 ms 235068 KB Output is correct
3 Correct 107 ms 235116 KB Output is correct
4 Correct 107 ms 235076 KB Output is correct
5 Correct 108 ms 235144 KB Output is correct
6 Correct 108 ms 235192 KB Output is correct
7 Correct 110 ms 235212 KB Output is correct
8 Correct 110 ms 235152 KB Output is correct
9 Correct 113 ms 235388 KB Output is correct
10 Correct 108 ms 235188 KB Output is correct
11 Correct 109 ms 235164 KB Output is correct
12 Correct 110 ms 235212 KB Output is correct
13 Correct 110 ms 235188 KB Output is correct
14 Correct 115 ms 235112 KB Output is correct
15 Correct 108 ms 235212 KB Output is correct
16 Correct 111 ms 235212 KB Output is correct
17 Correct 110 ms 235280 KB Output is correct
18 Correct 113 ms 235220 KB Output is correct
19 Correct 111 ms 235360 KB Output is correct
20 Correct 109 ms 235388 KB Output is correct
21 Correct 112 ms 235388 KB Output is correct
22 Correct 109 ms 235348 KB Output is correct
23 Correct 109 ms 235340 KB Output is correct
24 Correct 111 ms 235300 KB Output is correct
25 Correct 109 ms 235212 KB Output is correct
26 Correct 109 ms 235112 KB Output is correct
27 Incorrect 114 ms 235452 KB Output isn't correct
28 Halted 0 ms 0 KB -