oj.uz

Submission #464535

# Submission time Handle Problem Language Result Execution time Memory
464535 2021-08-13T11:15:09 Z amunduzbaev Game (eJOI20_game) C++14
20 / 100
 1 ms 460 KB 
#include "bits/stdc++.h"
using namespace std;

const int N = 25;
vector<int> edges[N*N], cycle, path;
int used[N*N], cntv, cnte;

map<array<int, 4>, int> mem;

//~ 0 cycle
//~ 1 path
//~      cycle, path, left for us, type

int rec(int i, int j, int left, int t){
	//~ cout<<i<<" "<<j<<" "<<left<<" "<<t<<"\n";
	if(i + 1 == (int)cycle.size() && j + 1 == (int)path.size()) return left;
	if(mem.count({i, j, left, t})) return mem[{i, j, left, t}];
	int& res = mem[{i, j, left, t}];
	res = -1e9;
	
	if(t == 0 && left >= 4){
		res = max(res, left - 4 - rec(i, j, 4, -1));
	} if(t == 1 && left > 2){
		res = max(res, left - 2 - rec(i, j, 2, -1));
	}
	
	if(i + 1 < (int)cycle.size()){
		res = max(res, left - rec(i + 1, j, cycle[i + 1], 0));
	} if(j + 1 < (int)path.size()){
		res = max(res, left - rec(i, j + 1, path[j + 1], 1));
	}
	
	return res;
}

void dfs(int u){ used[u] = 1;
	cntv++;
	cnte += (int)edges[u].size();
	for(auto x : edges[u]){
		if(used[x]) continue;
		dfs(x);
	}
}

void solve(){
	int n, m; cin>>n>>m;
	vector<string> h(n+1), v(m);
	for(int i=0;i<n+1;i++) cin>>h[i];
	for(int i=0;i<m;i++) cin>>v[i];
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int u = i * m + j;
			if(i && h[i][j] == '0') edges[u].push_back(u - m);
			if(i + 1 < n && h[i+1][j] == '0') edges[u].push_back(u + m);
			if(j && v[i][j] == '0') edges[u].push_back(u - 1);
			if(j + 1 < m && v[i][j+1] == '0') edges[u].push_back(u + 1);
			if(h[i][j] == '1' && h[i+1][j] == '1' && v[i][j] == '1' && v[i][j+1] == '1') used[i * m + j] = 1;
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int u = i *	m + j;
			if(used[u]) continue;
			cnte = cntv = 0;
			dfs(u);
			if(cntv * 2 > cnte) path.push_back(cntv);
			else cycle.push_back(cntv);
		}
	}
	
	sort(path.begin(), path.end());
	sort(cycle.begin(), cycle.end());
	
	//~ for(auto x : path) cout<<x<<" ";
	//~ cout<<"\n";
	
	//~ for(auto x : cycle) cout<<x<<" ";
	//~ cout<<"\n";
	
	cout<<rec(-1, -1, 0, -1)<<"\n";
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t = 1;
	//~ cin>>t;
	while(t--) solve();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Runtime error 1 ms 460 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Runtime error 1 ms 460 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -