oj.uz

Submission #233144

# Submission time Handle Problem Language Result Execution time Memory
233144 2020-05-19T14:32:02 Z Saboon Raspad (COI17_raspad) C++14
61 / 100
 1803 ms 604660 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; _ < 20; _++){
		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 294 ms 434040 KB Output is correct
2 Correct 294 ms 434296 KB Output is correct
3 Correct 294 ms 434168 KB Output is correct
4 Correct 295 ms 434424 KB Output is correct
5 Correct 296 ms 434192 KB Output is correct
6 Correct 292 ms 434296 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 434040 KB Output is correct
2 Correct 294 ms 434296 KB Output is correct
3 Correct 294 ms 434168 KB Output is correct
4 Correct 295 ms 434424 KB Output is correct
5 Correct 296 ms 434192 KB Output is correct
6 Correct 292 ms 434296 KB Output is correct
7 Correct 301 ms 435448 KB Output is correct
8 Correct 290 ms 434192 KB Output is correct
9 Correct 306 ms 435960 KB Output is correct
10 Correct 306 ms 436728 KB Output is correct
11 Correct 296 ms 435576 KB Output is correct
12 Correct 300 ms 435576 KB Output is correct
13 Correct 300 ms 435704 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 455928 KB Output is correct
2 Correct 648 ms 496852 KB Output is correct
3 Correct 745 ms 501496 KB Output is correct
4 Correct 583 ms 501244 KB Output is correct
5 Correct 374 ms 450296 KB Output is correct
6 Correct 567 ms 492408 KB Output is correct
7 Correct 593 ms 507128 KB Output is correct
8 Correct 557 ms 489080 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 434040 KB Output is correct
2 Correct 294 ms 434296 KB Output is correct
3 Correct 294 ms 434168 KB Output is correct
4 Correct 295 ms 434424 KB Output is correct
5 Correct 296 ms 434192 KB Output is correct
6 Correct 292 ms 434296 KB Output is correct
7 Correct 301 ms 435448 KB Output is correct
8 Correct 290 ms 434192 KB Output is correct
9 Correct 306 ms 435960 KB Output is correct
10 Correct 306 ms 436728 KB Output is correct
11 Correct 296 ms 435576 KB Output is correct
12 Correct 300 ms 435576 KB Output is correct
13 Correct 300 ms 435704 KB Output is correct
14 Correct 453 ms 455928 KB Output is correct
15 Correct 648 ms 496852 KB Output is correct
16 Correct 745 ms 501496 KB Output is correct
17 Correct 583 ms 501244 KB Output is correct
18 Correct 374 ms 450296 KB Output is correct
19 Correct 567 ms 492408 KB Output is correct
20 Correct 593 ms 507128 KB Output is correct
21 Correct 557 ms 489080 KB Output is correct
22 Correct 1202 ms 549236 KB Output is correct
23 Incorrect 1803 ms 604660 KB Output isn't correct
24 Halted 0 ms 0 KB -