oj.uz

Submission #377608

# Submission time Handle Problem Language Result Execution time Memory
377608 2021-03-14T11:30:25 Z negar_a Raspad (COI17_raspad) C++14
26 / 100
 6000 ms 23916 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 = 3e5 + 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 7 ms 9708 KB Output is correct
2 Correct 14 ms 9836 KB Output is correct
3 Correct 9 ms 9836 KB Output is correct
4 Correct 11 ms 9836 KB Output is correct
5 Correct 11 ms 9836 KB Output is correct
6 Correct 11 ms 9836 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 14 ms 9836 KB Output is correct
3 Correct 9 ms 9836 KB Output is correct
4 Correct 11 ms 9836 KB Output is correct
5 Correct 11 ms 9836 KB Output is correct
6 Correct 11 ms 9836 KB Output is correct
7 Correct 360 ms 10220 KB Output is correct
8 Correct 11 ms 9836 KB Output is correct
9 Correct 812 ms 10216 KB Output is correct
10 Correct 173 ms 10220 KB Output is correct
11 Correct 560 ms 10220 KB Output is correct
12 Correct 135 ms 10092 KB Output is correct
13 Correct 409 ms 10092 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6092 ms 23916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 14 ms 9836 KB Output is correct
3 Correct 9 ms 9836 KB Output is correct
4 Correct 11 ms 9836 KB Output is correct
5 Correct 11 ms 9836 KB Output is correct
6 Correct 11 ms 9836 KB Output is correct
7 Correct 360 ms 10220 KB Output is correct
8 Correct 11 ms 9836 KB Output is correct
9 Correct 812 ms 10216 KB Output is correct
10 Correct 173 ms 10220 KB Output is correct
11 Correct 560 ms 10220 KB Output is correct
12 Correct 135 ms 10092 KB Output is correct
13 Correct 409 ms 10092 KB Output is correct
14 Execution timed out 6092 ms 23916 KB Time limit exceeded
15 Halted 0 ms 0 KB -