Submission #209709

#	Time	Username	Problem	Language	Result	Execution time	Memory
209709		alishahali1382	Raspad (COI17_raspad)	C++14	100 / 100	2907 ms	53372 KiB

raspad

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int N = 100010, M=50;
typedef array<int, M> shit;

struct DSU{
	int n, comp;
	vector<int> par;
	DSU(int nn):n(nn), comp(n){
		par.resize(n);
		iota(all(par), 0);
	}
	void reset(){
		iota(all(par), 0);
		comp=n;
	}
	void comper(){
		comp=0;
		for (int i=0; i<n; i++) comp+=(par[i]==i);
	}
	int get(int x){
		if (par[x]==x) return x;
		return par[x]=get(par[x]);
	}
	int join(int x, int y){
		x=get(x);
		y=get(y);
		if (x==y) return 0;
		if (x>y) swap(x, y);
		par[y]=x;
		comp--;
		return 1;
	}
};

ll n, m, k, u, v, x, y, t, a, b, ans;
bool A[N][M];
int id[N][M], cnt;
map<shit, ll> mp1, mp2;

shit to_shit(DSU &dsu){
	shit res;
	for (int i=0; i<m; i++) res[i]=dsu.get(i);
	return res;
}

void print(shit sh){
	for (int i=0; i<m; i++) cerr<<sh[i]<<' ';cerr<<'\n';
}

void divide(int tl, int tr){
	if (tr-tl<1) return ;
	if (tr-tl==1){
		ans++;
		for (int i=1; i<m; i++) ans+=(!A[tl][i] || !A[tl][i-1]);
		return ;
	}
	ll mid=(tl+tr)>>1;
	divide(tl, mid);
	divide(mid, tr);
	/*
	debug2(tl, tr)
	debug(ans)
	*/
	cnt=0;
	for (int i=mid-1; i>=tl; i--) for (int j=0; j<m; j++) id[i][j]=cnt++;
	DSU dsu1(cnt);
	
	cnt=0;
	for (int i=mid; i<tr; i++) for (int j=0; j<m; j++) id[i][j]=cnt++;
	DSU dsu2(cnt);
	
	mp1.clear();
	mp2.clear();
		
	for (int i=mid-1; i>=tl; i--){
		for (int j=1; j<m; j++) if (A[i][j] && A[i][j-1]) dsu1.join(id[i][j], id[i][j-1]);
		if (i!=mid-1){
			for (int j=0; j<m; j++) if (A[i][j] && A[i+1][j]) dsu1.join(id[i][j], id[i+1][j]); 
		}
		ans+=1ll*(tr-mid)*(dsu1.comp-m*(i-tl));
		mp1[to_shit(dsu1)]++;
	}
	
	for (int i=mid; i<tr; i++){
		for (int j=1; j<m; j++) if (A[i][j] && A[i][j-1]) dsu2.join(id[i][j], id[i][j-1]);
		if (i!=mid){
			for (int j=0; j<m; j++) if (A[i][j] && A[i-1][j]) dsu2.join(id[i][j], id[i-1][j]); 
		}
		ans+=1ll*(mid-tl)*(dsu2.comp-(tr-1-i)*m);
		mp2[to_shit(dsu2)]++;
	}
	
	//debug(ans)
	
	for (auto it1:mp1) for (auto it2:mp2){
		DSU dsu(2*m);
		for (int i=0; i<m; i++) dsu.par[i]=it1.first[i];
		for (int i=0; i<m; i++) dsu.par[i+m]=it2.first[i]+m;
		
		ll cnt=0;
		for (int i=0; i<m; i++) if (A[mid][i] && A[mid-1][i] && dsu.join(i, m+i)) cnt++;
		cnt*=it1.second*it2.second;
		ans-=cnt;
	}
	//debug(ans)
	
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	char ch;
	for (int i=1; i<=n; i++) for (int j=0; j<m; j++) cin>>ch, A[i][j]=(ch=='1');
	divide(1, n+1);
	for (int i=1; i<=n; i++) for (int j=0; j<m; j++) if (!A[i][j]) ans-=i*(n+1-i);
	cout<<ans<<'\n';
	
	return 0;
}
/*
2 2
01
10

*/

Compilation message (stderr)

raspad.cpp: In function 'void print(shit)':
raspad.cpp:69:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i=0; i<m; i++) cerr<<sh[i]<<' ';cerr<<'\n';
  ^~~
raspad.cpp:69:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i=0; i<m; i++) cerr<<sh[i]<<' ';cerr<<'\n';
                                           ^~~~

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