oj.uz

Submission #370197

# Submission time Handle Problem Language Result Execution time Memory
370197 2021-02-23T14:53:18 Z soroush Raspad (COI17_raspad) C++14
26 / 100
 6000 ms 13036 KB 
//*
#pragma GCC optimize("O2")
//#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , m;
int a[maxn][51];
int par[maxn * 51];

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

bool merge(int u , int v){
	if((u = getpar(u)) == (v = getpar(v)))
		return(0);
	par[u] = v;
	return(1);
}

ll solve(int st){
	ll ans = 0 , sum = 0;
	for(int i = st ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++)
			ans += a[i][j] , par[i*m + j] = i * m + j;
		if(i^st)
			for(int j = 1 ; j <= m ; j ++)
				if(a[i][j] && a[i - 1][j])
					ans -= merge(i * m + j , i * m - m + j);
		for(int j = 2 ; j <= m ; j ++)
			if(a[i][j] && a[i][j - 1])
				ans -= merge(i * m + j , i * m + j - 1);
		sum += ans;
	}
	return(sum);
}

int32_t main(){
	migmig;
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= m ; j ++){
			char c;
			cin >> c;
			a[i][j] = (c == '1');
		}
	ll ans = 0;
	for(int i = 1 ; i <= n ; i ++)
		ans += solve(i);
	cout << ans;
	return(0);
}

Subtask #1
9.0 / 9.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 227 ms 768 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 547 ms 876 KB Output is correct
10 Correct 124 ms 780 KB Output is correct
11 Correct 351 ms 748 KB Output is correct
12 Correct 83 ms 620 KB Output is correct
13 Correct 264 ms 748 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 227 ms 768 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 547 ms 876 KB Output is correct
10 Correct 124 ms 780 KB Output is correct
11 Correct 351 ms 748 KB Output is correct
12 Correct 83 ms 620 KB Output is correct
13 Correct 264 ms 748 KB Output is correct
14 Execution timed out 6056 ms 13036 KB Time limit exceeded
15 Halted 0 ms 0 KB -