oj.uz

답안 #370306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
370306 2021-02-23T17:15:42 Z AriaH Raspad (COI17_raspad) C++17
61 / 100
 6000 ms 100976 KB 
/** Im the best because i work as hard as i possibly can **/
 
#pragma GCC optimize("O2, unroll-loops")
#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];

/// unify tp = 0 for the left side  &   unify tp = 1 for right side     unify2 for the merge of left and right

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

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

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

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

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;
}

ll jam(int l, int r, int tp, int mid)
{
	if(tp == 0)
	{
		r ++;
		return (l > mid? 0 : ps[l]) - (r > mid? 0 : ps[r]);
	}
	else
	{
		l --;
		return (r <= mid? 0 : ps[r]) - (l <= mid? 0 : ps[l]);
	}
}

inline void Reset(int x)  { par2[x] = x; }

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];
			arr[i][j] = 0;
		}
	}
	///printf("l = %d r = %d\n", l, r);
	vector < int > L, R;
	/// compressing the right side
	R.push_back(mid + 1);
	for(int i = mid + 1; i <= r; i ++)
	{
		for(int j = 1; j <= m; j ++)
		{
			cnt[i] += A[i][j];
			cnt[i] -= unify(I[i][j], I[i][j - 1], 1);
		}
		if(i > mid + 1)
		{
			cnt[i] += cnt[i - 1];
			for(int j = 1; j <= m; j ++)
			{
				cnt[i] -= unify(I[i][j], I[i - 1][j], 1);
			}
		}
		ps[i] = cnt[i];
		for(int j = 1; j <= m; j ++)
		{
			arr[i][j] = get(I[mid + 1][j]);
		}
		if(i > mid + 1)
		{
			ps[i] += ps[i - 1];
			int flag = 0;
			for(int j = 1; j <= m; j ++)
			{
				if(!A[mid + 1][j]) continue;
				if(arr[i][j] != arr[i - 1][j]) flag = 1;
			}
			if(flag) R.push_back(i);
		}
	}
	R.push_back(r + 1);
	/// end
	/// compressing the left side
	L.push_back(mid);
	for(int i = mid; i >= l; i --)
	{
		for(int j = 1; j <= m; j ++)
		{
			cnt[i] += A[i][j];
			cnt[i] -= unify(I[i][j], I[i][j - 1], 0);
		}
		if(i < mid)
		{
			cnt[i] += cnt[i + 1];
			for(int j = 1; j <= m; j ++)
			{
				cnt[i] -= unify(I[i][j], I[i + 1][j], 0);
			}
		}
		ps[i] = cnt[i];
		for(int j = 1; j <= m; j ++)
		{
			arr[i][j] = get(I[mid][j]);
		}
		if(i < mid)
		{
			ps[i] += ps[i + 1];
			int flag = 0;
			for(int j = 1; j <= m; j ++)
			{
				if(!A[mid][j]) continue;
				if(arr[i][j] != arr[i + 1][j]) flag = 1;
			}
			if(flag) L.push_back(i);
		}
	}
	L.push_back(l - 1);
	/// end
	/*printf("arr : \n");
	for(int i = l; i <= r; i ++)
	{
		printf("i = %d\n", i);
		for(int j = 1; j <= m; j ++)
		{
			printf("%d ", arr[i][j]);
		}
		printf("\n");
	}
	printf("ps & cnt\n");
	for(int i = l; i <= r; i ++)
	{
		printf("%lld %lld   ", cnt[i], ps[i]);
	}
	printf("\n showing L & R\n");
	for(auto x : L) printf("%d ", x);
	printf("\n");
	for(auto x : R) printf("%d ", x);
	printf("\n");
	*/
	for(int i1 = 0; i1 < SZ(L) - 1; i1 ++)
	{
		for(int i2 = 0; i2 < SZ(R) - 1; i2 ++)
		{
			for(int j = 1; j <= m; j ++)
			{
				Reset(arr[L[i1]][j]); Reset(arr[R[i2]][j]);
			}
			ll yal = 0;
			for(int j = 1; j <= m; j ++)
			{
				yal += unify2(arr[L[i1]][j], arr[R[i2]][j]);
			}
			///printf("i1 = %d i2 = %d yal = %lld jamleft = %lld jam right = %lld\n", i1, i2, yal, jam(L[i1 + 1] + 1, L[i1], 0, mid), jam(R[i2], R[i2 + 1] - 1, 1, mid));
			ll szl = (L[i1] - L[i1 + 1]), szr = R[i2 + 1] - R[i2];
			tot += jam(L[i1 + 1] + 1, L[i1], 0, mid) * szr +  jam(R[i2], R[i2 + 1] - 1, 1, mid) * szl - yal * szl * szr;
		}
	}
	///printf("tot = %lld\n", tot);
}
 
int main()
{
	scanf("%d%d", &n, &m);
	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:3:40: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("O2, unroll-loops")
      |                                        ^
raspad.cpp:37:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   37 | inline int ok(int i) { return A[RI[i].F][RI[i].S]; }
      |                    ^
raspad.cpp:39:15: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   39 | int get2(int x) { return (x == par2[x]? x : par2[x] = get2(par2[x])); }
      |               ^
raspad.cpp:41:14: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   41 | int get(int x) { return (x == par[x]? x : par[x] = get(par[x])); }
      |              ^
raspad.cpp:43:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   43 | int unify(int v, int u, int tp)
      |                               ^
raspad.cpp:60:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   60 | int unify2(int v, int u)
      |                        ^
raspad.cpp:69:37: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   69 | ll jam(int l, int r, int tp, int mid)
      |                                     ^
raspad.cpp:83:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   83 | inline void Reset(int x)  { par2[x] = x; }
      |                        ^
raspad.cpp:85:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   85 | void solve(int l, int r)
      |                        ^
raspad.cpp:225:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  225 | int main()
      |          ^
raspad.cpp: In function 'int main()':
raspad.cpp:227:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  227 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
raspad.cpp:238:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  238 |   scanf("%s", C);
      |   ~~~~~^~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 4 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 17 ms 1644 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 45 ms 1772 KB Output is correct
10 Correct 11 ms 1516 KB Output is correct
11 Correct 25 ms 1772 KB Output is correct
12 Correct 18 ms 1388 KB Output is correct
13 Correct 25 ms 1644 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 509 ms 42824 KB Output is correct
2 Correct 1095 ms 86764 KB Output is correct
3 Correct 1520 ms 86688 KB Output is correct
4 Correct 614 ms 77932 KB Output is correct
5 Correct 281 ms 26220 KB Output is correct
6 Correct 1123 ms 86508 KB Output is correct
7 Correct 936 ms 86508 KB Output is correct
8 Correct 809 ms 69356 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 4 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 17 ms 1644 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 45 ms 1772 KB Output is correct
10 Correct 11 ms 1516 KB Output is correct
11 Correct 25 ms 1772 KB Output is correct
12 Correct 18 ms 1388 KB Output is correct
13 Correct 25 ms 1644 KB Output is correct
14 Correct 509 ms 42824 KB Output is correct
15 Correct 1095 ms 86764 KB Output is correct
16 Correct 1520 ms 86688 KB Output is correct
17 Correct 614 ms 77932 KB Output is correct
18 Correct 281 ms 26220 KB Output is correct
19 Correct 1123 ms 86508 KB Output is correct
20 Correct 936 ms 86508 KB Output is correct
21 Correct 809 ms 69356 KB Output is correct
22 Correct 2592 ms 100976 KB Output is correct
23 Execution timed out 6079 ms 96860 KB Time limit exceeded
24 Halted 0 ms 0 KB -