oj.uz

Submission #235619

# Submission time Handle Problem Language Result Execution time Memory
235619 2020-05-28T20:33:07 Z ArshiaDadras Raspad (COI17_raspad) C++14
61 / 100
 6000 ms 10872 KB 
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, M = 50 + 5;
map<vector<int>, long long> mp[2];
map<vector<int>, int> dp[2];
int n, m, par[M], idx[M];
char c[N][M];

int get_par(int u) {
	return ~par[u]? par[u] = get_par(par[u]): u;
}

void merge(int u, int v) {
	u = get_par(u);
	v = get_par(v);
	if (u == v)
		return;
	if (u > v)
		swap(u, v);
	par[v] = u;
}

vector<int> merge(vector<int> A, vector<int> B) {
	memset(par, -1, sizeof par);
	memset(idx, -1, sizeof idx);
	for (int i = 0; i < m; i++)
		if (~A[i] && ~B[i]) {
			if (!~idx[B[i]])
				idx[B[i]] = A[i];
			merge(A[i], idx[B[i]]);
		}
	for (int i = 0; i < m; i++)
		if (~A[i])
			A[i] = get_par(A[i]);
	return A;
}

void read_input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> c[i];
}

void solve() {
	long long ans = 0;
	for (int i = n - 1; ~i; i--) {
		int ted = 0;
		vector<int> help(m);
		for (int j = 0; j < m; j++) {
			if (j && c[i][j] ^ '0' && c[i][j - 1] ^ '0')
				help[j] = help[j - 1];
			else
				help[j] = c[i][j] ^ '0'? j: -1;
			ted += help[j] == j;
		}
		dp[i & 1].clear(), mp[i & 1].clear();
		dp[i & 1][help]++, mp[i & 1][help] = ted;
		for (auto [vec, k]: dp[i & 1 ^ 1]) {
			vector<int> A = merge(help, vec);
			vector<int> B = merge(vec, help);
			for (int j = ted = 0; j < m; j++) {
				ted -= vec[j] == j;
				ted += A[j] == j;
			}
			memset(idx, -1, sizeof idx);
			for (int j = 0; j < m; j++)
				if (~B[j])
					idx[B[j]] = max(idx[B[j]], A[j]);
			for (int j = 0; j < m; j++)
				if (B[j] == j)
					ted += !~idx[B[j]];
			mp[i & 1][A] += mp[i & 1 ^ 1][vec];
			mp[i & 1][A] += 1LL * k * ted;
			dp[i & 1][A] += k;
		}
		for (auto [vec, k]: mp[i & 1])
			ans += k;
	}
	cout << ans;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve();
	return 0;
}

Compilation message

raspad.cpp: In function 'void solve()':
raspad.cpp:60:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [vec, k]: dp[i & 1 ^ 1]) {
             ^
raspad.cpp:60:28: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   for (auto [vec, k]: dp[i & 1 ^ 1]) {
                          ~~^~~
raspad.cpp:74:25: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    mp[i & 1][A] += mp[i & 1 ^ 1][vec];
                       ~~^~~
raspad.cpp:78:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [vec, k]: mp[i & 1])
             ^
raspad.cpp:78:20: warning: unused variable 'vec' [-Wunused-variable]
   for (auto [vec, k]: mp[i & 1])
                    ^

Subtask #1
9.0 / 9.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 23 ms 512 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 14 ms 512 KB Output is correct
12 Correct 31 ms 384 KB Output is correct
13 Correct 18 ms 384 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3740 KB Output is correct
2 Correct 161 ms 7336 KB Output is correct
3 Correct 371 ms 7296 KB Output is correct
4 Correct 95 ms 6656 KB Output is correct
5 Correct 51 ms 2432 KB Output is correct
6 Correct 230 ms 7296 KB Output is correct
7 Correct 511 ms 7416 KB Output is correct
8 Correct 180 ms 5888 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 23 ms 512 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 14 ms 512 KB Output is correct
12 Correct 31 ms 384 KB Output is correct
13 Correct 18 ms 384 KB Output is correct
14 Correct 55 ms 3740 KB Output is correct
15 Correct 161 ms 7336 KB Output is correct
16 Correct 371 ms 7296 KB Output is correct
17 Correct 95 ms 6656 KB Output is correct
18 Correct 51 ms 2432 KB Output is correct
19 Correct 230 ms 7296 KB Output is correct
20 Correct 511 ms 7416 KB Output is correct
21 Correct 180 ms 5888 KB Output is correct
22 Correct 426 ms 7928 KB Output is correct
23 Correct 2033 ms 10764 KB Output is correct
24 Correct 1720 ms 10764 KB Output is correct
25 Correct 416 ms 10752 KB Output is correct
26 Correct 439 ms 10752 KB Output is correct
27 Correct 709 ms 9728 KB Output is correct
28 Correct 1578 ms 9848 KB Output is correct
29 Correct 810 ms 10872 KB Output is correct
30 Execution timed out 6060 ms 10752 KB Time limit exceeded
31 Halted 0 ms 0 KB -