oj.uz

Submission #463934

# Submission time Handle Problem Language Result Execution time Memory
463934 2021-08-12T04:26:12 Z amunduzbaev Game (eJOI20_game) C++14
0 / 100
 18 ms 24044 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());
		}
	}
	
	sort(tt.begin(), tt.end());
	
	for(auto x : tt) cout<<x<<" ";
	cout<<"\n";


	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";
}

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 Incorrect 18 ms 24012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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