oj.uz

Submission #235620

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

const int N = 1e5 + 5, M = 50 + 5;
unordered_map<string, long long> mp[2];
unordered_map<string, 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;
}

string merge(string A, string 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;
		string help;
		for (int j = 0; j < m; j++) {
			if (j && c[i][j] ^ '0' && c[i][j - 1] ^ '0')
				help += help[j - 1];
			else
				help += 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]) {
			string A = merge(help, vec);
			string 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]], (int) 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 'std::__cxx11::string merge(std::__cxx11::string, std::__cxx11::string)':
raspad.cpp:30:18: warning: array subscript has type 'char' [-Wchar-subscripts]
    if (!~idx[B[i]])
                  ^
raspad.cpp:31:13: warning: array subscript has type 'char' [-Wchar-subscripts]
     idx[B[i]] = A[i];
             ^
raspad.cpp:32:24: warning: array subscript has type 'char' [-Wchar-subscripts]
    merge(A[i], idx[B[i]]);
                        ^
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:70:14: warning: array subscript has type 'char' [-Wchar-subscripts]
      idx[B[j]] = max(idx[B[j]], (int) A[j]);
              ^
raspad.cpp:70:30: warning: array subscript has type 'char' [-Wchar-subscripts]
      idx[B[j]] = max(idx[B[j]], (int) A[j]);
                              ^
raspad.cpp:73:23: warning: array subscript has type 'char' [-Wchar-subscripts]
      ted += !~idx[B[j]];
                       ^
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 4 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 5 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 17 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 11 ms 384 KB Output is correct
12 Correct 18 ms 512 KB Output is correct
13 Correct 13 ms 384 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3072 KB Output is correct
2 Correct 132 ms 5760 KB Output is correct
3 Correct 269 ms 5764 KB Output is correct
4 Correct 72 ms 5120 KB Output is correct
5 Correct 42 ms 1920 KB Output is correct
6 Correct 174 ms 5772 KB Output is correct
7 Correct 297 ms 5772 KB Output is correct
8 Correct 125 ms 4728 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 17 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 11 ms 384 KB Output is correct
12 Correct 18 ms 512 KB Output is correct
13 Correct 13 ms 384 KB Output is correct
14 Correct 47 ms 3072 KB Output is correct
15 Correct 132 ms 5760 KB Output is correct
16 Correct 269 ms 5764 KB Output is correct
17 Correct 72 ms 5120 KB Output is correct
18 Correct 42 ms 1920 KB Output is correct
19 Correct 174 ms 5772 KB Output is correct
20 Correct 297 ms 5772 KB Output is correct
21 Correct 125 ms 4728 KB Output is correct
22 Correct 367 ms 4700 KB Output is correct
23 Correct 1519 ms 5768 KB Output is correct
24 Correct 1405 ms 5772 KB Output is correct
25 Correct 350 ms 5880 KB Output is correct
26 Correct 374 ms 5856 KB Output is correct
27 Correct 545 ms 5880 KB Output is correct
28 Correct 1194 ms 6008 KB Output is correct
29 Correct 659 ms 5880 KB Output is correct
30 Correct 3698 ms 5880 KB Output is correct
31 Correct 211 ms 10872 KB Output is correct
32 Correct 1786 ms 10752 KB Output is correct
33 Correct 762 ms 9720 KB Output is correct
34 Correct 981 ms 9720 KB Output is correct