oj.uz

Submission #26312

# Submission time Handle Problem Language Result Execution time Memory
26312 2017-06-29T07:04:22 Z 김동현(#1101) Raspad (COI17_raspad) C++14
26 / 100
 2779 ms 27124 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, m, p[51000], chk[100010][51];
char b[100010][51];
ll ans, cans;

int fnd(int x){ return p[x] = (x == p[x] ? x : fnd(p[x])); }
void uni(int x, int y){
	if(fnd(x) == fnd(y)) return;
	cans--; p[fnd(x)] = fnd(y);
}

int num(int x, int y){ return (x - 1) * m + y; }

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%s", b[i] + 1);
		for(int j = 1; j <= m * i; j++) p[j] = j;
		cans = 0;
		for(int j = i; j >= 1; j--){
			for(int k = 1; k <= m; k++){
				if(b[j][k] != '1') continue;
				cans++;
				chk[j][k] = i;
				for(int d = 0; d < 4; d++){
					if(chk[j + dx[d]][k + dy[d]] == i && 
					   b[j + dx[d]][k + dy[d]] == '1') uni(num(j, k), num(j + dx[d], k + dy[d]));
				}
			}
			ans += cans;
		}
	}
	printf("%lld\n", ans);
}

Compilation message

raspad.cpp: In function 'int main()':
raspad.cpp:19:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
raspad.cpp:21:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", b[i] + 1);
                        ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27124 KB Output is correct
2 Correct 6 ms 27124 KB Output is correct
3 Correct 3 ms 27124 KB Output is correct
4 Correct 0 ms 27124 KB Output is correct
5 Correct 3 ms 27124 KB Output is correct
6 Correct 3 ms 27124 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27124 KB Output is correct
2 Correct 6 ms 27124 KB Output is correct
3 Correct 3 ms 27124 KB Output is correct
4 Correct 0 ms 27124 KB Output is correct
5 Correct 3 ms 27124 KB Output is correct
6 Correct 3 ms 27124 KB Output is correct
7 Correct 253 ms 27124 KB Output is correct
8 Correct 0 ms 27124 KB Output is correct
9 Correct 639 ms 27124 KB Output is correct
10 Correct 186 ms 27124 KB Output is correct
11 Correct 406 ms 27124 KB Output is correct
12 Correct 109 ms 27124 KB Output is correct
13 Correct 323 ms 27124 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 2779 ms 27124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27124 KB Output is correct
2 Correct 6 ms 27124 KB Output is correct
3 Correct 3 ms 27124 KB Output is correct
4 Correct 0 ms 27124 KB Output is correct
5 Correct 3 ms 27124 KB Output is correct
6 Correct 3 ms 27124 KB Output is correct
7 Correct 253 ms 27124 KB Output is correct
8 Correct 0 ms 27124 KB Output is correct
9 Correct 639 ms 27124 KB Output is correct
10 Correct 186 ms 27124 KB Output is correct
11 Correct 406 ms 27124 KB Output is correct
12 Correct 109 ms 27124 KB Output is correct
13 Correct 323 ms 27124 KB Output is correct
14 Runtime error 2779 ms 27124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -