oj.uz

Submission #370132

# Submission time Handle Problem Language Result Execution time Memory
370132 2021-02-23T10:59:42 Z AriaH Raspad (COI17_raspad) C++11
61 / 100
 6000 ms 104008 KB 
/** Im the best because i work as hard as i possibly can **/

///#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"
#define SZ(x)						(int)x.size()

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
const int M = 52;

char C[N];

int n, m, A[N][M], I[N][M], par[N * M], arr[N][M], par2[N * M];

pii RI[N * M];

ll tot, ps[N], cnt[N];

int get(int x) { return ((x == par[x])? x : par[x] = get(par[x])); }

inline int ok(int i)
{
	return A[RI[i].F][RI[i].S];
}

inline int unify(int v, int u)
{
	if(!ok(v) || !ok(u)) return 0;
	if(u < v) swap(u, v);
	v = get(v), u = get(u);
	if(v == u) return 0;
	par[u] = v;
	return 1;
}

int get2(int x) { return ((x == par2[x])? x : par2[x] = get2(par2[x])); }


inline int unify2(int v, int u)
{
	if(!ok(v) || !ok(u)) return 0;
	v = get2(v), u = get2(u);
	if(v == u) return 0;
	par2[u] = v;
	return 1;
}

void solve(int l, int r)
{
	if(l > r) return;
	if(l == r)
	{
		for(int j = 1; j <= m; j ++)
		{
			tot += A[l][j];
			tot -= (A[l][j] + A[l][j - 1] == 2);
		}
		return;
	}
	int mid = (l + r) >> 1;
	solve(l, mid); solve(mid + 1, r);
	cnt[l - 1] = cnt[r + 1] = ps[l - 1] = ps[r + 1] = 0;
	for(int i = l; i <= r; i ++)
	{
		ps[i] = cnt[i] = 0;
		for(int j = 1; j <= m; j ++)
		{
			par[I[i][j]] = I[i][j];
			par2[I[i][j]] = I[i][j];
			arr[i][j] = 0;
		}
	}
	vector < ll > merges;
	merges.push_back(mid + 1);
	for(int i = mid + 1; i <= r; i ++)
	{
		if(i > mid + 1) cnt[i] = cnt[i - 1];
		for(int j = 1; j <= m; j ++)
		{
			cnt[i] += A[i][j];
			cnt[i] -= unify(I[i][j], I[i][j - 1]);
		}
		if(i > mid + 1)
		{
			for(int j = 1; j <= m; j ++)
			{
				cnt[i] -= unify(I[i][j], I[i - 1][j]);
			}
		}
		for(int j = 1; j <= m; j ++) arr[i][j] = get(I[mid + 1][j]);
		if(i > mid + 1)
		{
			int flag = 0;
			for(int j = 1; j <= m; j ++)
			{
				if(A[mid + 1][j] == 0) continue;
				if(arr[i][j] != arr[i - 1][j]) flag = 1;
			}
			if(flag) merges.push_back(i);
		}
		ps[i] = cnt[i] + (i > mid + 1? ps[i - 1] : 0);
	}
	merges.push_back(r + 1);
	ll cu = 0;
	for(int i = mid; i >= l; i --)
	{
		for(int j = 1; j <= m; j ++)
		{
			cu += A[i][j];
			cu -= unify(I[i][j], I[i][j - 1]);
		}
		if(i < mid)
		{
			for(int j = 1; j <= m; j ++)
			{
				cu -= unify(I[i][j], I[i + 1][j]);
			}
		}
		for(int id = 0; id < SZ(merges) - 1; id ++)
		{
			for(int j = 1; j <= m; j ++)
			{
				par2[get(I[mid][j])] = get(I[mid][j]);
				par2[arr[merges[id]][j]] = arr[merges[id]][j];
			}
			ll yal = 0;
			for(int j = 1; j <= m; j ++)
			{
				if((A[mid][j] + A[mid + 1][j]) < 2) continue;
				ll v = get(I[mid][j]), u = arr[merges[id]][j];
				yal += unify2(v, u);
			}
			tot += 1ll * (cu - yal) * (merges[id + 1] - merges[id]) + (ps[merges[id + 1] - 1] - ps[merges[id] - 1]);
		}
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	RI[0] = Mp(0, 0);
	for(int i = 1; i <= n; i ++)
	{
	    for(int j = 1; j <= m; j ++)
	    {
		I[i][j] = (i - 1) * m + j;
		RI[I[i][j]] = Mp(i, j);
	    }
	}
	for(int i = 1; i <= n; i ++)
	{
		scanf("%s", C);
		for(int j = 0; j < m; j ++)
		{
			A[i][j + 1] = (C[j] == '1');
		}
	}
	solve(1, n);
	printf("%lld\n", tot);
	return 0;
}

Compilation message

raspad.cpp: In function 'int main()':
raspad.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
raspad.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  169 |   scanf("%s", C);
      |   ~~~~~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 4 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 4 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 17 ms 1644 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 101 ms 1900 KB Output is correct
10 Correct 12 ms 1644 KB Output is correct
11 Correct 33 ms 1772 KB Output is correct
12 Correct 30 ms 1516 KB Output is correct
13 Correct 40 ms 1664 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 42676 KB Output is correct
2 Correct 997 ms 86636 KB Output is correct
3 Correct 3340 ms 86520 KB Output is correct
4 Correct 502 ms 79512 KB Output is correct
5 Correct 256 ms 26860 KB Output is correct
6 Correct 1234 ms 88172 KB Output is correct
7 Correct 1475 ms 88172 KB Output is correct
8 Correct 930 ms 70704 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 4 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 17 ms 1644 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 101 ms 1900 KB Output is correct
10 Correct 12 ms 1644 KB Output is correct
11 Correct 33 ms 1772 KB Output is correct
12 Correct 30 ms 1516 KB Output is correct
13 Correct 40 ms 1664 KB Output is correct
14 Correct 491 ms 42676 KB Output is correct
15 Correct 997 ms 86636 KB Output is correct
16 Correct 3340 ms 86520 KB Output is correct
17 Correct 502 ms 79512 KB Output is correct
18 Correct 256 ms 26860 KB Output is correct
19 Correct 1234 ms 88172 KB Output is correct
20 Correct 1475 ms 88172 KB Output is correct
21 Correct 930 ms 70704 KB Output is correct
22 Correct 2845 ms 104008 KB Output is correct
23 Execution timed out 6011 ms 92968 KB Time limit exceeded
24 Halted 0 ms 0 KB -