oj.uz

답안 #303446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
303446 2020-09-20T10:14:57 Z pit4h Dango Maker (JOI18_dango_maker) C++14
0 / 100
 1 ms 384 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 3001;
int matched[N * N], vis[N * N];
int iter;
bool connected[N * N];
bool match(int x, vector<vector<int>>& g) {
	vis[x] = iter;
	for(int i: g[x]) {
		if(matched[i] == -1) {
			matched[i] = x;
			return true;
		}
	}
	for(int i: g[x]) {
		if(vis[i] != iter && match(matched[i], g)) {
			matched[i] = x;
			return true;
		}
	}
	return false;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; cin>>n>>m;
	vector<string> tab(n);
	for(int i=0; i<n; ++i) {
		cin>>tab[i];
	}
	vector<vector<bool>> horiz(n, vector<bool>(m)), vert(n, vector<bool>(m));
	for(int i=0; i<n; ++i) { // left - right
		for(int j=0; j+2<m; ++j) {
			if(tab[i][j] == 'R' && tab[i][j+1] == 'G' && tab[i][j+2] == 'W') {
				vert[i][j] = 1;
			}
		}
	}
	vector<vector<int>> rep(n, vector<int>(m));
	int nr = 0;
	for(int i=0; i+2<n; ++i) { // top - bottom 
		for(int j=0; j<m; ++j) {
			if(tab[i][j] == 'R' && tab[i+1][j] == 'G' && tab[i+2][j] == 'W') {
				horiz[i][j] = 1;
				rep[i][j] = nr;
				nr++;
			}
		}
	}
	vector<vector<int>> g;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<m; ++j) {
			if(vert[i][j]) {
				g.push_back({});
				if(horiz[i][j]) {
					g.back().push_back(rep[i][j]);
					connected[rep[i][j]] = 1;
				}
				if(i-1>=0 && j+1<n && horiz[i-1][j+1]) {
					g.back().push_back(rep[i-1][j+1]);
					connected[rep[i-1][j+1]] = 1;
				}
				if(i-2>=0 && j+2<n && horiz[i-2][j+2]) {
					g.back().push_back(rep[i-2][j+2]);
					connected[rep[i-2][j+2]] = 1;
				}
			}
		}
	}
	for(int i=0; i<nr; ++i) {
		matched[i] = -1;
	}
	int sz = g.size();
	int ans = 0;
	int n1 = 0, n2 = 0, isolated = 0;
	for(int i=0; i<sz; ++i) {
		iter++;
		match(i, g);
		if(g[i].empty()) {
			ans++;
			isolated++;
		}
		else n1++;
	}
	for(int i=0; i<nr; ++i) {
		if(matched[i] != -1 || !connected[i]) {
			ans++;
			if(!connected[i]) isolated++;
		}
		else n2++;
	}
	n1 -= ans;
	cout<<max(ans, isolated + n1 + n1);
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Incorrect 0 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Incorrect 0 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Incorrect 0 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -