Submission #685282

#	Time	Username	Problem	Language	Result	Execution time	Memory
685282		GusterGoose27	Raspad (COI17_raspad)	C++11	26 / 100	170 ms	135364 KiB

raspad

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

const int MAXN = 1e5+2;
const int MAXM = 52;

int cur_r = 0;
ll ans = 0;

class edge {
public:
	int x, y, w;
	edge(int x, int y, int w) : x(x), y(y), w(w){}
};

int uf[MAXN*MAXM];
int rnk[MAXN*MAXM];
pii top[MAXN*MAXM];
int row_req[MAXN][MAXM]; // first row where it is no longer the top
bool active[MAXN+1][MAXM];
vector<edge> adj[2]; // mst
vector<pii> edges[MAXM];
int dist[MAXM][MAXM];
int to_comp[MAXN+1][MAXM];
int miniuf[MAXM];
int lft[MAXM+1];
int dpth[MAXM];

vector<int> up_adj[MAXM/2];
bool cur = 0;
int n, m;

int find(int i) {
	return (uf[i] == -1) ? i : (uf[i] = find(uf[i]));
}

int mfind(int i) {
	return (miniuf[i] == -1) ? i : (miniuf[i] = mfind(miniuf[i]));
}

bool operator<(edge &a, edge &b) {
	return a.w < b.w;
}

void minimerge(int a, int b, int d) {
	a = mfind(a);
	b = mfind(b);
	if (a == b) return;
	if (lft[a] < lft[b]) dpth[lft[b]] = d;
	else dpth[lft[a]] = d;
	miniuf[a] = b;
	lft[b] = min(lft[a], lft[b]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (top[a] < top[b]) row_req[top[b].first][top[b].second] = cur_r;
	else row_req[top[a].first][top[a].second] = cur_r;
	if (rnk[a] < rnk[b]) swap(a, b);
	uf[b] = a;
	if (rnk[a] == rnk[b]) rnk[a]++;
	top[a] = min(top[a], top[b]);
}

int hsh(int i, int j) {
	return m*i+j;
}

void make_dists(int cur, int topval, int sz, int p = -1, int block = 0) {
	if (cur != topval && cur < sz) {
		dist[topval][cur] = block;
		return;
	}
	for (pii e: edges[cur]) {
		int nxt = e.first;
		if (nxt == p) continue;
		make_dists(nxt, topval, sz, cur, max(block, e.second));
	}
}

void construct(int sz) {
	vector<edge> mst2;
	for (int i = 0; i < sz; i++) {
		fill(dist[i], dist[i]+sz, n);
		make_dists(i, i, sz);
		for (int j = 0; j < i; j++) mst2.push_back(edge(i, j, dist[i][j]));
	}
	sort(mst2.begin(), mst2.end());
	fill(miniuf, miniuf+sz, -1);
	for (edge e: mst2) {
		int a = mfind(e.x);
		int b = mfind(e.y);
		if (a != b) {
			adj[cur].push_back(e);
			miniuf[a] = b;
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		for (int j = 0; j < m; j++) {
			active[i][j] = s[j]-'0';
			top[hsh(i, j)] = pii(i, j);
			row_req[i][j] = n;
		}
	}
	fill(uf, uf+n*m, -1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m-1; j++) {
			if (active[i][j] && active[i][j+1]) merge(hsh(i, j), hsh(i, j+1));
		}
		cur_r++;
		if (i < n-1) {
			for (int j = 0; j < m; j++) {
				if (active[i][j] && active[i+1][j]) merge(hsh(i, j), hsh(i+1, j));
			}
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (active[i][j]) ans += (ll) i*(row_req[i][j]-i);
		}
	}
	// cout << ans << "\n";
	int prevcnt = 0;
	for (int i = n-1; i >= 0; i--) {
		vector<pii> ranges;
		for (int j = 0; j < prevcnt; j++) {
			up_adj[j].clear();
		}
		int pl = -2;
		int pr = -2;
		for (int j = 0; j < m; j++) {
			if (!active[i][j]) continue;
			if (j > pr+1) {
				if (pl != -2) {
					ranges.push_back(pii(pl, pr));
				}
				pl = j;
				pr = j-1;
			}
			pr++;
			if (active[i+1][j]) up_adj[to_comp[i+1][j]].push_back(ranges.size());
			to_comp[i][j] = ranges.size();
		}
		if (pl != -2) {
			ranges.push_back(pii(pl, pr));
		}
		if (ranges.size()) {
			adj[cur].clear();
			vector<edge> mst_edges;
			for (int j = 0; j < ranges.size(); j++) {
				miniuf[j] = -1;
				lft[j] = j;
				dpth[j] = n;
				edges[j].clear();
			}
			for (int j = 0; j < prevcnt; j++) {
				miniuf[j+ranges.size()] = -1;
				lft[j+ranges.size()] = ranges.size();
				for (int a: up_adj[j]) mst_edges.push_back(edge(a, j+ranges.size(), i+1));
				edges[j+ranges.size()].clear();
			}
			for (edge e: adj[!cur]) mst_edges.push_back(edge(e.x+ranges.size(), e.y+ranges.size(), e.w));
			for (edge e: mst_edges) {
				int a = e.x;
				int b = e.y;
				if (mfind(a) != mfind(b)) {
					minimerge(a, b, e.w);
					edges[a].push_back(pii(b, e.w));
					edges[b].push_back(pii(a, e.w));
				}
			} // we have a tree, and we want to simplify it
			for (int j = 0; j < ranges.size()-1; j++) {
				int k = j+1;
				if (mfind(j) != mfind(k)) {
					minimerge(j, k, n);
					edges[j].push_back(pii(k, n));
					edges[k].push_back(pii(j, n));
				}
			}
			construct(ranges.size());
			ll sub = 0;
			for (int j = 0; j < ranges.size(); j++) {
				sub += (dpth[j]-i);
			}
			// cout << sub << "\n";
			ans += sub;
		}
		prevcnt = ranges.size();
		cur = !cur;
	}
	cout << ans << "\n";
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:164:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |    for (int j = 0; j < ranges.size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
raspad.cpp:186:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |    for (int j = 0; j < ranges.size()-1; j++) {
      |                    ~~^~~~~~~~~~~~~~~~~
raspad.cpp:196:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |    for (int j = 0; j < ranges.size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~

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