oj.uz

Submission #26314

# Submission time Handle Problem Language Result Execution time Memory
26314 2017-06-29T07:07:06 Z imsifile Raspad (COI17_raspad) C++
100 / 100
 1806 ms 126060 KB 
#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

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.0 / 9.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 126060 KB Output is correct
2 Correct 0 ms 126060 KB Output is correct
3 Correct 0 ms 126060 KB Output is correct
4 Correct 0 ms 126060 KB Output is correct
5 Correct 0 ms 126060 KB Output is correct
6 Correct 0 ms 126060 KB Output is correct
7 Correct 3 ms 126060 KB Output is correct
8 Correct 0 ms 126060 KB Output is correct
9 Correct 9 ms 126060 KB Output is correct
10 Correct 3 ms 126060 KB Output is correct
11 Correct 6 ms 126060 KB Output is correct
12 Correct 3 ms 126060 KB Output is correct
13 Correct 6 ms 126060 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 126060 KB Output is correct
2 Correct 426 ms 126060 KB Output is correct
3 Correct 606 ms 126060 KB Output is correct
4 Correct 276 ms 126060 KB Output is correct
5 Correct 103 ms 126060 KB Output is correct
6 Correct 443 ms 126060 KB Output is correct
7 Correct 319 ms 126060 KB Output is correct
8 Correct 339 ms 126060 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 126060 KB Output is correct
2 Correct 0 ms 126060 KB Output is correct
3 Correct 0 ms 126060 KB Output is correct
4 Correct 0 ms 126060 KB Output is correct
5 Correct 0 ms 126060 KB Output is correct
6 Correct 0 ms 126060 KB Output is correct
7 Correct 3 ms 126060 KB Output is correct
8 Correct 0 ms 126060 KB Output is correct
9 Correct 9 ms 126060 KB Output is correct
10 Correct 3 ms 126060 KB Output is correct
11 Correct 6 ms 126060 KB Output is correct
12 Correct 3 ms 126060 KB Output is correct
13 Correct 6 ms 126060 KB Output is correct
14 Correct 176 ms 126060 KB Output is correct
15 Correct 426 ms 126060 KB Output is correct
16 Correct 606 ms 126060 KB Output is correct
17 Correct 276 ms 126060 KB Output is correct
18 Correct 103 ms 126060 KB Output is correct
19 Correct 443 ms 126060 KB Output is correct
20 Correct 319 ms 126060 KB Output is correct
21 Correct 339 ms 126060 KB Output is correct
22 Correct 976 ms 126060 KB Output is correct
23 Correct 1806 ms 126060 KB Output is correct
24 Correct 1709 ms 126060 KB Output is correct
25 Correct 1089 ms 126060 KB Output is correct
26 Correct 879 ms 126060 KB Output is correct
27 Correct 1012 ms 126060 KB Output is correct
28 Correct 1413 ms 126060 KB Output is correct
29 Correct 1466 ms 126060 KB Output is correct
30 Correct 873 ms 126060 KB Output is correct
31 Correct 906 ms 126060 KB Output is correct
32 Correct 736 ms 126060 KB Output is correct
33 Correct 989 ms 126060 KB Output is correct
34 Correct 1279 ms 126060 KB Output is correct