oj.uz

답안 #684609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684609 2023-01-22T01:09:24 Z GusterGoose27 Raspad (COI17_raspad) C++11
26 / 100
 178 ms 132004 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

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

const int MAXN = 1e5;
const int MAXM = 50;

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/2][MAXM/2];
int to_comp[MAXN+1][MAXM];
int miniuf[MAXM];
int lft[MAXM+1];
int dpth[MAXM/2];

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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 596 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 6 ms 2516 KB Output is correct
8 Correct 1 ms 732 KB Output is correct
9 Correct 10 ms 2856 KB Output is correct
10 Correct 14 ms 2100 KB Output is correct
11 Correct 7 ms 2772 KB Output is correct
12 Correct 10 ms 2132 KB Output is correct
13 Correct 10 ms 2616 KB Output is correct

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 59028 KB Output is correct
2 Incorrect 178 ms 132004 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 6 ms 2516 KB Output is correct
8 Correct 1 ms 732 KB Output is correct
9 Correct 10 ms 2856 KB Output is correct
10 Correct 14 ms 2100 KB Output is correct
11 Correct 7 ms 2772 KB Output is correct
12 Correct 10 ms 2132 KB Output is correct
13 Correct 10 ms 2616 KB Output is correct
14 Correct 70 ms 59028 KB Output is correct
15 Incorrect 178 ms 132004 KB Output isn't correct
16 Halted 0 ms 0 KB -