Submission #233146

#	Time	Username	Problem	Language	Result	Execution time	Memory
233146		Saboon	Raspad (COI17_raspad)	C++14	100 / 100	2101 ms	770296 KiB

raspad

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<long double> point;
 
const int maxn = 100000 + 10;
const int maxm = 50 + 5;
 
string s[maxn];
vector<int> g[maxn*maxm], G[maxn*maxm];
int a[maxn][maxm], h[maxn*maxm];
pair<int,int> p[maxn*maxm];
int lo[maxn*maxm], hi[maxn*maxm];
vector<int> C[maxn*maxm];
int par[maxn*maxm], match[maxn*maxm], dis[maxn*maxm];
int pre[maxn*maxm];

int get_par(int v){
	return par[v] < 0 ? v : par[v] = get_par(par[v]);
}
 
void merge(int v, int u){
	if ((v = get_par(v)) == (u = get_par(u)))
		return;
	if (v > u)
		swap(v, u);
	par[u] = v;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> s[i];
	int k = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (s[i][j] == '1' and (j == 0 or s[i][j-1] == '0')){
				a[i][j] = k;
				p[k ++] = {i,j};
			}
			if (s[i][j] == '0')
				continue;
			if (j > 0 and s[i][j-1] == '1')
				a[i][j] = a[i][j-1];
			else
				a[i][j] = a[i][j];
			h[a[i][j]] = i;
			if (i > 0 and s[i-1][j] == '1'){
				g[a[i][j]].push_back(a[i-1][j]);
				G[a[i-1][j]].push_back(a[i][j]);
			}
		}
	}
	for (int i = 0; i < k; i++)
		lo[i] = i - 1, hi[i] = k;
	for (int _ = 0; _ < 23; _++){
		for (int i = 0; i < k; i++){
			if (hi[i] - lo[i] == 1)
				continue;
			int mid = (lo[i] + hi[i]) >> 1;
			C[mid].push_back(i);
		}
		memset(par, -1, sizeof par);
		for (int i = 0; i < k; i++){
			for (auto j : g[i])
				merge(i, j);
			for (auto j : C[i]){
				if (get_par(j) < j)
					hi[j] = i;
				else
					lo[j] = i;
			}
			C[i].clear();
		}
	}
	h[k] = n;
	ll answer = 0;
	for (int i = 0; i < k; i++)
		answer += 1ll * h[i] * (h[hi[i]] - h[i]);
	memset(par, -1, sizeof par);
	memset(match, -1, sizeof match);
	for (int i = k-1; i >= 0; i--){
		if (i == k-1 or h[i] != h[i+1]){
			for (int j = i; j >= 0 and h[j] == h[i]; j--){
				for (auto k : G[j])
					merge(k, G[j][0]);
			}
		}
		int mnm = k;
		for (auto j : G[i])
			mnm = min(mnm, get_par(j));
		if (h[mnm] == h[i]){
			match[mnm] = i;
			pre[i] = mnm;
		}
		for (auto j : G[i])
			merge(i, j);
	}
	for (int i = k-1; i >= 0; i--){
		if (match[i] == -1){
			answer += n - h[i];
			continue;
		}	
		int lef = G[match[i]][0], rig = G[match[i]].back();
		if (rig == G[i][0]){
			dis[i] = 1;
			answer += 1;
			continue;
		}
		int x = i;
		bool found = 0;
		while (dis[i] == 0){
			for (auto j : G[x]){
				while (rig < match[j]){
					dis[j] = max(dis[j], dis[match[j]]);
					match[j] = match[match[j]];
				}
				if (match[j] == -1)
					continue;
				found = 1;
				dis[i] = dis[j] + 1;
				answer += dis[i];
				break;
			}
			x = pre[x];
		}
	}
	cout << answer << endl;
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:107:7: warning: unused variable 'lef' [-Wunused-variable]
   int lef = G[match[i]][0], rig = G[match[i]].back();
       ^~~
raspad.cpp:114:8: warning: variable 'found' set but not used [-Wunused-but-set-variable]
   bool found = 0;
        ^~~~~

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