oj.uz

Submission #66335

# Submission time Handle Problem Language Result Execution time Memory
66335 2018-08-10T08:59:24 Z ekrem Raspad (COI17_raspad) C++
0 / 100
 6000 ms 46152 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000007
#define N 100005
using namespace std;

int n, m, grp, b[N], a[N][60], u[N][60];
long long ans;
int o[] = {0, 0, 1, -1};
int p[] = {-1, 1, 0, 0};
char x;

void cikar(int grup){
	for(int i = 1; i <= n; i++){
		b[i] = 0;
		for(int j = 1; j <= m; j++)
			if(u[i][j - 1] != grup and u[i][j] == grup)
				b[i]++;
	}
}

void dfs(int i, int j){
	u[i][j] = grp;
	for(int k = 0; k < 4; k++)
		if(a[i + o[k]][j + p[k]] and !u[i + o[k]][j + p[k]])
			dfs(i + o[k], j + p[k]);
}

void bul(){
	for(int i = 1; i <= n; i++){
		int mn = inf;
		for(int j = i; j <= n; j++){
			if(b[j])
				mn = min(mn, b[j]);
			ans += mn;
			// cout << mn << endl;
		}
	}
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&m);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++){
			scanf(" %c",&x);
			if(x == '1')
				a[i][j] = 1;
		}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(!u[i][j] and a[i][j]){
				grp++;
				dfs(i, j);
				cikar(grp);
				bul();
				// for(int of = 1; of <= n; of++)cout << b[of] << " ";cout << endl;
			}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

raspad.cpp: In function 'int main()':
raspad.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n ,&m);
  ~~~~~^~~~~~~~~~~~~~~~
raspad.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&x);
    ~~~~~^~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 6 ms 488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 6 ms 488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1818 ms 46152 KB Output is correct
2 Execution timed out 6069 ms 46152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 6 ms 488 KB Output isn't correct
3 Halted 0 ms 0 KB -