Submission #56703

#	Time	Username	Problem	Language	Result	Execution time	Memory
56703		polyfish	Raspad (COI17_raspad)	C++14	0 / 100	152 ms	4460 KiB

raspad

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 100002;
const int MAX_M = 52;

struct event {
	int a, b, row;

	event() {}
	event(int a, int b, int row):
		a(a), b(b), row(row) {}

	bool operator<(const event& T) {
		return row>T.row;
	}
};

struct dsu {
	int cnt_0, cnt_1;
	vector<int> lab;
	vector<bool> left_side;

	void clear(int _n) {
		cnt_0 = cnt_1 = 0;
		lab.clear();
		left_side.clear();
		lab.resize(_n+1);
		left_side.resize(_n+1);
	}

	int findset(int u) {
		return lab[u]<=0 ? u : lab[u] = findset(lab[u]);
	}

	void uni(int s, int t) {
		s = findset(s);
		t = findset(t);
		if (s==t)
            return;
		if (lab[s]>lab[t])
            swap(s, t);
        if (lab[s]==lab[t])
            --lab[s];
        lab[t] = s;
        if (left_side[t] && left_side[s])
            --cnt_1;
        else
            --cnt_0;
	}
};

int n, m, f[2][MAX_M][MAX_M];
char a[MAX_M][MAX_N];
dsu D;
vector<event> E;

void enter() {
	scanf("%d%d\n", &m, &n);
	for (int i=1; i<=m; ++i) {
		for (int j=1; j<=n; ++j) {
			a[j][i] = getchar();
		}
		getchar();
	}
	swap(m, n);
}

void solve() {
	int64_t res = 0;
	int p = 0;
	for (int c=1; c<=n; ++c) {
		p ^= 1;
		for (int i=1; i<=m; ++i)
			if (a[i][c]=='1')
				f[p][i][i] = c;
            else
                f[p][i][i] = 0;
		for (int i=m; i>=1; --i) {
			for (int j=i+1; j<=m; ++j) {
				if (i!=j && a[i][c]!='0' && a[j][c]!='0')
					f[p][j][i] = f[p][i][j] = max(max(f[p][i+1][j], f[p][i][j-1]), f[p^1][i][j]);
                else
                    f[p][i][j] = f[p][i][j] = 0;
			}
		}
		D.clear(m);
		for (int i=1; i<=m; ++i) {
			if (a[i][c]=='1')
				++D.cnt_0;
			if (c<n && a[i][c]=='1' && a[i][c+1]=='1') {
				--D.cnt_0;
				++D.cnt_1;
				D.left_side[i] = true;
			}
		}
		E.clear();
		for (int i=1; i<=m; ++i) {
			for (int j=i+1; j<=m; ++j) {
				if (i!=j && f[p][i][j]>0 && f[p][i][j]<c) {
					E.push_back(event(i, j, f[p][i][j]));
				}
				if (i!=j && f[p][i][j]==c)
                    D.uni(i, j);
			}
		}
		sort(E.begin(), E.end());
		int _prev = c;
		for (int i=0; i<E.size(); ++i) {
			res += D.cnt_0 * (n - c + 1) * (_prev - E[i].row);
			res += D.cnt_1 * (_prev - E[i].row);
			int j = i - 1;
			while (j+1<E.size() && E[j+1].row == E[i].row) {
				++j;
				D.uni(E[j].a, E[j].b);
			}
			_prev = E[i].row;
			i = j;
		}
		res += D.cnt_0 * (n - c + 1) * _prev;
		res += D.cnt_1 *_prev;
	}
	cout << res;
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		//freopen(FILE_NAME".out", "w", stdout);
	#endif
	enter();
	solve();
}

Compilation message (stderr)

raspad.cpp: In function 'void solve()':
raspad.cpp:85:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
             else
             ^~~~
raspad.cpp:87:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   for (int i=m; i>=1; --i) {
   ^~~
raspad.cpp:92:32: warning: operation on 'f[p][i][j]' may be undefined [-Wsequence-point]
                     f[p][i][j] = f[p][i][j] = 0;
                     ~~~~~~~~~~~^~~~~~~~~~~~~~~~
raspad.cpp:117:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<E.size(); ++i) {
                 ~^~~~~~~~~
raspad.cpp:121:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (j+1<E.size() && E[j+1].row == E[i].row) {
           ~~~^~~~~~~~~
raspad.cpp: In function 'void enter()':
raspad.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d\n", &m, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39