oj.uz

Submission #377607

# Submission time Handle Problem Language Result Execution time Memory
377607 2021-03-14T11:29:34 Z negar_a Raspad (COI17_raspad) C++14
26 / 100
 827 ms 1644 KB 
//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 1e4 + 10, N = 55;
int par[maxn * N];
int t[maxn];
int cnt[maxn][N];
string s[maxn];

int get_par(int x){
	if(x == par[x]){
		return x;
	}
	return par[x] = get_par(par[x]);
}

void merge(int x, int y){
	x = get_par(x);
	y = get_par(y);
	par[x] = y;
}

int main(){
	fast_io;
	int n, m;
	cin >> n >> m;
	int c = 0;
	for(int i = 0; i < n; i ++){
		cin >> s[i];
		for(int j = 0; j < m; j ++){
			t[i] += (s[i][j] == '1');
		}
	}
	ll ans = 0;
	for(int T = 0; T < n; T ++){
		c = 0;
		for(int i = 0; i < n; i ++){
			for(int j = 0; j < m; j ++){
				if(s[i][j] == '1'){
					cnt[i][j] = c;
					par[c] = c;
					c ++;
				}
			}
		}
		int an = 0;
		for(int j = T; j < n; j ++){
			an += t[j];
//			cout << "p: " << ans << endl;
			for(int k = 0; k < m; k ++){
				if(s[j][k] == '1'){
					if((j > T) && s[j - 1][k] == '1'){
						if(get_par(cnt[j][k]) != get_par(cnt[j - 1][k])){
							merge(cnt[j][k], cnt[j - 1][k]);
							an --;
						}
					}
					if(k < m - 1 && s[j][k + 1] == '1'){
						if(get_par(cnt[j][k]) != get_par(cnt[j][k + 1])){
							merge(cnt[j][k], cnt[j][k + 1]);
							an --;
						}
					}
				}
			}
			ans += an;
		}
//		cout << "ans = " << ans << endl;
	}
	cout << ans;
	
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 7 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 4 ms 748 KB Output is correct
5 Correct 6 ms 748 KB Output is correct
6 Correct 5 ms 748 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 7 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 4 ms 748 KB Output is correct
5 Correct 6 ms 748 KB Output is correct
6 Correct 5 ms 748 KB Output is correct
7 Correct 366 ms 1084 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 827 ms 1260 KB Output is correct
10 Correct 168 ms 1132 KB Output is correct
11 Correct 549 ms 1132 KB Output is correct
12 Correct 143 ms 1132 KB Output is correct
13 Correct 400 ms 1120 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1644 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 7 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 4 ms 748 KB Output is correct
5 Correct 6 ms 748 KB Output is correct
6 Correct 5 ms 748 KB Output is correct
7 Correct 366 ms 1084 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 827 ms 1260 KB Output is correct
10 Correct 168 ms 1132 KB Output is correct
11 Correct 549 ms 1132 KB Output is correct
12 Correct 143 ms 1132 KB Output is correct
13 Correct 400 ms 1120 KB Output is correct
14 Runtime error 3 ms 1644 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -