oj.uz

Submission #463936

# Submission time Handle Problem Language Result Execution time Memory
463936 2021-08-12T04:36:21 Z amunduzbaev Game (eJOI20_game) C++14
0 / 100
 40 ms 48572 KB 
#include "bits/stdc++.h"
using namespace std;

const int N = 1e3 + 5;
vector<int> edges[N*N], cmp;
int used[N*N], block[N*N]	;

void dfs(int u){
	cmp.push_back(u);
	used[u] = 1;
	for(auto x : edges[u]){
		if(used[x]) continue;
		dfs(x);
	}
}

void solve(){
	int n, m; cin>>n>>m;
	for(int i=0;i<=n;i++){
		for(int j=1;j<=m;j++){
			char state; cin>>state;
			if(state == '0'){
				if(i && i < n){
					int a = (i - 1) * n + j, b = i * n + j;
					edges[a].push_back(b);
					edges[b].push_back(a);
				}
			} else {
				if(i) block[(i - 1) * n + j]++;
				if(i < n) block[i * n + j]++;
			}
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<=m;j++){
			char state; cin>>state;
			if(state == '0'){
				if(j && j < m){
					int a = i * n + j, b = i * n + j + 1;
					edges[a].push_back(b);
					edges[b].push_back(a);
				}
			} else {
				if(j) block[i * n + j]++;
				if(j < m) block[i * n + j + 1]++;
			}
		}
	}
	
	vector<int> tt;
	for(int i=0;i<n;i++){
		for(int j=1;j<=m;j++){
			if(used[i * n + j]) continue;
			if(block[i * n + j] == 4) continue;
			cmp.clear();
			dfs(i * n + j);
			
			tt.push_back((int)cmp.size());
		}
	}

	assert((int)tt.size() == 1);

	sort(tt.begin(), tt.end());
	array<int, 2> res = {0, 0};
	for(int i=0;i<(int)tt.size();i++){
		res[i&1] += tt[i];
	}
	
	cout<<res[1] - res[0]<<"\n";
}

/*

3 3
111
111
111
111
1111
1111
1111

*/

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24012 KB Output is correct
2 Runtime error 39 ms 48516 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23984 KB Output is correct
2 Runtime error 40 ms 48480 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 48572 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 48520 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24012 KB Output is correct
2 Runtime error 39 ms 48516 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -