oj.uz

답안 #232319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232319 2020-05-16T17:11:49 Z pedy4000 Raspad (COI17_raspad) C++14
26 / 100
 534 ms 632 KB 
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int N = 1e3 + 3;
int n, m;
ll ans;
int num, cnt;
int par[N * N];
string s[N];
int Arr[N];

int root (int v) {
	return (par[v] == v? v: par[v] = root(par[v]));
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> s[i];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			Arr[j] = -1;
		num = 0;
		cnt = 0;

		for (int j = 0; j < m; j++)
			if (s[i][j] == '1') {
				Arr[j] = num;
				par[num] = num;
				num++;
				cnt++;
			}

		for (int j = 0; j + 1 < m; j++)
			if (s[i][j] == '1' && s[i][j + 1] == '1') {
				par[root(Arr[j])] = root(Arr[j + 1]);
				cnt--;
			}

		ans += cnt;
		for (int j = i + 1; j < n; j++) {
			for (int k = 0; k < m; k++) {
				if (s[j][k] == '0')
					Arr[k] = -1;
				else {
					if (Arr[k] == -1) {
						Arr[k] = num;
						par[num] = num;
						num++;
						cnt++;
					}
				}
			}
			for (int k = 0; k + 1 < m; k++)
				if (s[j][k] == '1' && s[j][k + 1] == '1' && root(Arr[k]) != root(Arr[k + 1])) {
					par[root(Arr[k])] = root(Arr[k + 1]);
					cnt--;
				}
				
			ans += cnt;
		}
	}

	cout << ans << "\n";
	return 0;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 207 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 534 ms 632 KB Output is correct
10 Correct 43 ms 384 KB Output is correct
11 Correct 330 ms 632 KB Output is correct
12 Correct 47 ms 504 KB Output is correct
13 Correct 250 ms 512 KB Output is correct

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 207 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 534 ms 632 KB Output is correct
10 Correct 43 ms 384 KB Output is correct
11 Correct 330 ms 632 KB Output is correct
12 Correct 47 ms 504 KB Output is correct
13 Correct 250 ms 512 KB Output is correct
14 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -