oj.uz

Submission #26302

# Submission time Handle Problem Language Result Execution time Memory
26302 2017-06-29T06:04:41 Z 서규호(#1103) Raspad (COI17_raspad) C++14
9 / 100
 6000 ms 71268 KB 
#include <bits/stdc++.h>

#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 1000000007
#define left lleft
#define right rright
#define Inf 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus

using namespace std;

int N,M,nn; lld ans;
int a[100002][52];
int where[100002][52],when[100002][52];
bool check[100002][52];
char s[100];
lld seg[400002];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

void update(int node,int l,int r,int s,int e,lld value){
	if(r < s || e < l || s > e) return;
	if(s <= l && r <= e){
		seg[node] += (value*(r-l+1));
		return;
	}
	int mid = (l+r)/2;
	update(node*2,l,mid,s,e,value);
	update(node*2+1,mid+1,r,s,e,value);
	seg[node] = seg[node*2]+seg[node*2+1];
}

int sx,ex;
void dfs(int x,int y){
	check[x][y] = true;
	for(int i=0; i<4; i++){
		if(x+dx[i] < sx || x+dx[i] > ex || y+dy[i] < 1 || y+dy[i] > M) continue;
		if(a[x+dx[i]][y+dy[i]] == 0 || check[x+dx[i]][y+dy[i]]) continue;
		dfs(x+dx[i],y+dy[i]);
	}
}
void process(int x,int y){
	sx = x; ex = y;
	for(int i=x; i<=y; i++){
		for(int j=1; j<=M; j++){
			if(check[i][j] || a[i][j] == 0) continue;
			dfs(i,j);
			ans++;
		}
	}
	for(int i=x; i<=y; i++) for(int j=1; j<=M; j++) check[i][j] = false;
}

int main(){
	scanf("%d %d",&N,&M);
	for(nn=1; nn<N; nn*=2);
	for(int i=1; i<=N; i++){
		scanf("%s",s);
		for(int j=1; j<=M; j++) a[i][j] = s[j-1]-'0';
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=i; j++){
			process(j,i);
		}
	}
	printf("%lld\n",ans);

	return 0;
}

Compilation message

raspad.cpp: In function 'int main()':
raspad.cpp:59:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
raspad.cpp:62:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s);
                ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 71160 KB Output is correct
2 Correct 273 ms 71160 KB Output is correct
3 Correct 119 ms 71160 KB Output is correct
4 Correct 79 ms 71160 KB Output is correct
5 Correct 139 ms 71160 KB Output is correct
6 Correct 163 ms 71160 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 71160 KB Output is correct
2 Correct 273 ms 71160 KB Output is correct
3 Correct 119 ms 71160 KB Output is correct
4 Correct 79 ms 71160 KB Output is correct
5 Correct 139 ms 71160 KB Output is correct
6 Correct 163 ms 71160 KB Output is correct
7 Execution timed out 6000 ms 71160 KB Execution timed out
8 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6000 ms 71268 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 71160 KB Output is correct
2 Correct 273 ms 71160 KB Output is correct
3 Correct 119 ms 71160 KB Output is correct
4 Correct 79 ms 71160 KB Output is correct
5 Correct 139 ms 71160 KB Output is correct
6 Correct 163 ms 71160 KB Output is correct
7 Execution timed out 6000 ms 71160 KB Execution timed out
8 Halted 0 ms 0 KB -