oj.uz

Submission #233146

# Submission time Handle Problem Language Result Execution time Memory
233146 2020-05-19T14:34:48 Z Saboon Raspad (COI17_raspad) C++14
100 / 100
 2101 ms 770296 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 306 ms 434040 KB Output is correct
2 Correct 306 ms 434296 KB Output is correct
3 Correct 300 ms 434168 KB Output is correct
4 Correct 299 ms 434424 KB Output is correct
5 Correct 303 ms 434172 KB Output is correct
6 Correct 310 ms 434296 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 434040 KB Output is correct
2 Correct 306 ms 434296 KB Output is correct
3 Correct 300 ms 434168 KB Output is correct
4 Correct 299 ms 434424 KB Output is correct
5 Correct 303 ms 434172 KB Output is correct
6 Correct 310 ms 434296 KB Output is correct
7 Correct 316 ms 435344 KB Output is correct
8 Correct 300 ms 434168 KB Output is correct
9 Correct 312 ms 435832 KB Output is correct
10 Correct 309 ms 436732 KB Output is correct
11 Correct 315 ms 435576 KB Output is correct
12 Correct 311 ms 435448 KB Output is correct
13 Correct 312 ms 435704 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 455928 KB Output is correct
2 Correct 679 ms 495720 KB Output is correct
3 Correct 783 ms 500472 KB Output is correct
4 Correct 599 ms 500300 KB Output is correct
5 Correct 392 ms 450552 KB Output is correct
6 Correct 593 ms 491384 KB Output is correct
7 Correct 618 ms 506136 KB Output is correct
8 Correct 577 ms 488312 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 434040 KB Output is correct
2 Correct 306 ms 434296 KB Output is correct
3 Correct 300 ms 434168 KB Output is correct
4 Correct 299 ms 434424 KB Output is correct
5 Correct 303 ms 434172 KB Output is correct
6 Correct 310 ms 434296 KB Output is correct
7 Correct 316 ms 435344 KB Output is correct
8 Correct 300 ms 434168 KB Output is correct
9 Correct 312 ms 435832 KB Output is correct
10 Correct 309 ms 436732 KB Output is correct
11 Correct 315 ms 435576 KB Output is correct
12 Correct 311 ms 435448 KB Output is correct
13 Correct 312 ms 435704 KB Output is correct
14 Correct 471 ms 455928 KB Output is correct
15 Correct 679 ms 495720 KB Output is correct
16 Correct 783 ms 500472 KB Output is correct
17 Correct 599 ms 500300 KB Output is correct
18 Correct 392 ms 450552 KB Output is correct
19 Correct 593 ms 491384 KB Output is correct
20 Correct 618 ms 506136 KB Output is correct
21 Correct 577 ms 488312 KB Output is correct
22 Correct 1256 ms 546396 KB Output is correct
23 Correct 1885 ms 599708 KB Output is correct
24 Correct 1785 ms 591992 KB Output is correct
25 Correct 1283 ms 557864 KB Output is correct
26 Correct 2061 ms 770296 KB Output is correct
27 Correct 1068 ms 555384 KB Output is correct
28 Correct 1462 ms 585976 KB Output is correct
29 Correct 1725 ms 605144 KB Output is correct
30 Correct 2101 ms 770296 KB Output is correct
31 Correct 2012 ms 750584 KB Output is correct
32 Correct 1225 ms 613240 KB Output is correct
33 Correct 1311 ms 591352 KB Output is correct
34 Correct 1398 ms 584056 KB Output is correct