Submission #26314

#	Time	Username	Problem	Language	Result	Execution time	Memory
26314		imsifile	Raspad (COI17_raspad)	C++98	100 / 100	1806 ms	126060 KiB

raspad

#include<stdio.h>
#include<vector>
#define MAX 5005005
#define grid(i,j) ((i)*M+(j))
using namespace std;

typedef long long lld;
int N, M; char mp[101010][55];
int tmp[MAX]; // always be 0
int cnum[101010][55];

struct uftree {
	int par[MAX], gas[MAX], ccn;
	int us[55], ucn;
	void init(int st, int en){
		for(int i=st; i<en; i++) par[i]=-1, gas[i]=0;
		ccn=0;
	}
	void set_us(const char* c, int row, int wid){
		ucn=0;
		for(int i=0; i<wid; i++){
			if(c[i]=='0') continue;
			if(i && c[i-1]=='1') continue;
			us[ucn++] = grid(row, i);
		}
	}
	void add(int ix){ par[ix]=-1; gas[ix]=1; ccn++; }
	int root(int ix){ return par[ix]<0 ? ix : par[ix]=root(par[ix]); }
	void connect(int n1, int n2){
		n1 = root(n1), n2 = root(n2);
		if(n1 == n2) return;
		if(gas[n1] > gas[n2]) par[n2]=n1, gas[n1]+=gas[n2];
		else par[n1]=n2, gas[n2]+=gas[n1];
		ccn--;
	}
	int condition(int* vs){
		int cnt=0;
		for(int i=0; i<ucn; i++){
			int r = root(us[i]);
			if(tmp[r]) vs[i]=tmp[r]-1;
			else vs[i]=-1, tmp[r]=i+1, cnt++;
		}
		for(int i=0; i<ucn; i++) tmp[root(us[i])]=0;
		return cnt;
	}
} up, dw;

int par[55], ccn;
int rt(int ix){ return par[ix]<0 ? ix : par[ix]=rt(par[ix]); }

lld dnq(int s, int e){
	int m = (s+e)/2; lld gap=0, cr=0;
	if(s > e) return 0;
	if(s == e){
		up.set_us(mp[s], s, M);
		return up.ucn;
	}
	gap = dnq(s, m-1) + dnq(m+1, e);

	up.init(grid(s,0), grid(m+1,0));
	up.set_us(mp[m], m, M);
	for(int i=m; i>=s; i--){
		for(int j=0; j<M; j++){
			if(mp[i][j]=='0')continue;
			up.add(grid(i,j));
			if(i<m && mp[i+1][j]=='1') up.connect(grid(i,j), grid(i+1,j));
			if(j>0 && mp[i][j-1]=='1') up.connect(grid(i,j), grid(i,j-1));
		}
		cr += (lld)(e-m+1) * (up.ccn - up.condition(cnum[i]));
	}

	dw.init(grid(m,0), grid(e+1,0));
	dw.set_us(mp[m], m, M);
	for(int i=m; i<=e; i++){
		for(int j=0; j<M; j++){
			if(mp[i][j]=='0')continue;
			dw.add(grid(i,j));
			if(i>m && mp[i-1][j]=='1') dw.connect(grid(i,j), grid(i-1,j));
			if(j>0 && mp[i][j-1]=='1') dw.connect(grid(i,j), grid(i,j-1));
		}
		cr += (lld)(m-s+1) * (dw.ccn - dw.condition(cnum[i]));
	}

	int ucn=1, uix[55]={m,}, dcn=1, dix[55]={m,}; vector<int> modi[55];
	for(int i=m-1; i>=s; i--){
		int j;
		for(j=0; j<up.ucn; j++) if(cnum[i][j]!=cnum[i+1][j]) break;
		if(j<up.ucn) uix[ucn++]=i;
	}
	uix[ucn++]=s-1;
	for(int i=m+1; i<=e; i++){
		int j, fl=0;
		for(j=0; j<dw.ucn; j++){
			if(cnum[i-1][j]<0 && cnum[i][j]>=0) fl=1, modi[dcn].push_back(j);
		}
		if(fl) dix[dcn++]=i;
	}
	dix[dcn++]=e+1;

	for(int i=0; i<ucn-1; i++){
		ccn = up.ucn;
		for(int j=0; j<up.ucn; j++){
			par[j] = cnum[uix[i]][j];
			if(par[j]>=0) ccn--;
		}
		for(int j=0; j<dcn-1; j++){
			for(int k=modi[j].size(); k--;){
				int a=modi[j][k], b=cnum[dix[j]][a];
				a=rt(a), b=rt(b);
				if(a!=b) par[b]=a, ccn--;
			}
			cr += (lld)(uix[i]-uix[i+1])*(dix[j+1]-dix[j])*ccn;
		}
	}

	return gap+cr;
}

int main(){
	scanf("%d%d\n", &N, &M);
	for(int i=0; i<N; i++) gets(mp[i]);

	printf("%lld\n", dnq(0, N-1));
	return 0;
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:121:25: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
  for(int i=0; i<N; i++) gets(mp[i]);
                         ^
In file included from raspad.cpp:1:0:
/usr/include/stdio.h:638:14: note: declared here
 extern char *gets (char *__s) __wur __attribute_deprecated__;
              ^
raspad.cpp:121:25: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
  for(int i=0; i<N; i++) gets(mp[i]);
                         ^
In file included from raspad.cpp:1:0:
/usr/include/stdio.h:638:14: note: declared here
 extern char *gets (char *__s) __wur __attribute_deprecated__;
              ^
raspad.cpp:121:35: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
  for(int i=0; i<N; i++) gets(mp[i]);
                                   ^
In file included from raspad.cpp:1:0:
/usr/include/stdio.h:638:14: note: declared here
 extern char *gets (char *__s) __wur __attribute_deprecated__;
              ^
raspad.cpp:120:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d\n", &N, &M);
                         ^
raspad.cpp:121:36: warning: ignoring return value of 'char* gets(char*)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) gets(mp[i]);
                                    ^
/tmp/cc0VWu8n.o: In function `main':
raspad.cpp:(.text.startup+0x3b): warning: the `gets' function is dangerous and should not be used.

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