Submission #463938

#	Time	Username	Problem	Language	Result	Execution time	Memory
463938		amunduzbaev	Game (eJOI20_game)	C++14	20 / 100	17 ms	24048 KiB

game

#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) * m + j, b = i * m + 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 * m + j, b = i * m + 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: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20