Submission #235620

#	Time	Username	Problem	Language	Result	Execution time	Memory
235620		ArshiaDadras	Raspad (COI17_raspad)	C++14	100 / 100	3698 ms	10872 KiB

raspad

/* 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 (stderr)

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 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39