oj.uz

Submission #463937

# Submission time Handle Problem Language Result Execution time Memory
463937 2021-08-12T04:38:20 Z amunduzbaev Game (eJOI20_game) C++14
0 / 100
 18 ms 24056 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) * m + j]++;
				if(i < n) block[i * m + 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 {
				block[i * m + j]++;
				block[i * m + j + 1]++;
			}
		}
	}
	
	vector<int> tt;
	for(int i=0;i<n;i++){
		for(int j=1;j<=m;j++){
			if(used[i * m + j]) continue;
			if(block[i * m + j] == 4) continue;
			cmp.clear();
			dfs(i * m + j);
			
			tt.push_back((int)cmp.size());
		}
	}

	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 23984 KB Output is correct
2 Correct 18 ms 24004 KB Output is correct
3 Correct 15 ms 24012 KB Output is correct
4 Correct 16 ms 24056 KB Output is correct
5 Correct 16 ms 24012 KB Output is correct
6 Incorrect 16 ms 24040 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24044 KB Output is correct
2 Correct 15 ms 23944 KB Output is correct
3 Incorrect 15 ms 24012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24012 KB Output is correct
2 Correct 14 ms 24012 KB Output is correct
3 Correct 14 ms 23972 KB Output is correct
4 Correct 14 ms 24036 KB Output is correct
5 Incorrect 14 ms 24012 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23984 KB Output is correct
2 Correct 18 ms 24004 KB Output is correct
3 Correct 15 ms 24012 KB Output is correct
4 Correct 16 ms 24056 KB Output is correct
5 Correct 15 ms 24044 KB Output is correct
6 Correct 15 ms 23944 KB Output is correct
7 Incorrect 15 ms 24012 KB Output isn't correct
8 Halted 0 ms 0 KB -