oj.uz

Submission #57370

# Submission time Handle Problem Language Result Execution time Memory
57370 2018-07-14T16:33:18 Z IvanC Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 199 ms 44900 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 60;
const int MAXL = 2*1e5 + 10;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
 
struct node{
	int pref[2],suf[2],componentes,s0,s1;
	
	node(int v0 = 0,int v1 = 0){
		pref[0] = v0;pref[1] = v1;
		suf[0] = v0;suf[1] = v1;
		s0 = v0;
		s1 = v1;
		componentes = max(s0,s1);
	}
	
	node operator+(const node& other )const{
		node novo;
		novo.pref[0] = pref[0];novo.pref[1] = pref[1];
		novo.suf[0] = other.suf[0];novo.suf[1] = suf[1];
		novo.s0 = s0 + other.s0;
		novo.s1 = s1 + other.s1;
		novo.componentes = componentes + other.componentes;
		int q1 = (suf[0] && other.pref[0]);
		int q2 = (suf[1] && other.pref[1]);
		novo.s0 -= q1;
		novo.s1 -= q2;
		int q3 = q1 || q2;
		novo.componentes--;
		return novo;
	}
	
};
 
int matriz[MAXN][MAXN],tamx,tamy;
int tabela[3][MAXL];
int processado[MAXN][MAXN];
int lo_x,lo_y,hi_x,hi_y;
node seg[4*MAXL];
 
inline int valido(int x,int y){
	return x >= lo_x && y >= lo_y && x <= hi_x && y <= hi_y && matriz[x][y] != 1; 
}
 
void dfs(int x,int y){
	if(processado[x][y]) return;
	//printf("DFS %d %d\n",x,y);
	processado[x][y] = 1;
	for(int i = 0;i<4;i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(valido(nx,ny)) dfs(nx,ny);
	}
}
 
void build(int pos,int left,int right){
	//printf("P %d L %d R %d\n",pos,left,right);
	if(left == right){
		seg[pos] = node(1 - tabela[1][left],1 - tabela[2][left]);
		return;
	}
	int mid = (left + right)/2;
	build(2*pos,left,mid);
	build(2*pos+1,mid+1,right);
	seg[pos] = seg[2*pos] + seg[2*pos+1];
}
 
node query(int pos,int left,int right,int i,int j){
	if(left >= i && right <= j){
		return seg[pos];
	}
	int mid = (left+right)/2;
	if(j <= mid) return query(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
	else return query(2*pos,left,mid,i,j) + query(2*pos+1,mid+1,right,i,j);
}
 
void init(int R, int C, int sr, int sc, int M, char *S) {
	tamx = R;tamy= C;
	if(tamx <= 50 && tamy <= 50){
		matriz[sr][sc] = 1;
		for(int vez = 0;vez<M;vez++){
			if(S[vez] == 'N'){
				//printf("N\n");
				sr--;
			}
			else if(S[vez] == 'W'){
				//printf("W\n");
				sc--;
			}
			else if(S[vez] == 'S'){
				//printf("S\n");
				sr++;
			}
			else{
				//printf("E\n");
				sc++;
			}
			//printf("%d %d\n",sr,sc);
			matriz[sr][sc] = 1;
		}
		//for(int i = 1;i<=tamx;i++){
		//	for(int j = 1;j<=tamy;j++){
		//		printf("%d",matriz[i][j]);
		//	}
		//	printf("\n");
		//}
	}
	else{
		tabela[sr][sc] = 1;
		for(int vez = 0;vez<M;vez++){
			if(S[vez] == 'N'){
				//printf("N\n");
				sr--;
			}
			else if(S[vez] == 'W'){
				//printf("W\n");
				sc--;
			}
			else if(S[vez] == 'S'){
				//printf("S\n");
				sr++;
			}
			else{
				//printf("E\n");
				sc++;
			}
			//printf("%d %d\n",sr,sc);
			tabela[sr][sc] = 1;
		}
		build(1,1,tamy);
	}
}
 
int colour(int ar, int ac, int br, int bc) {
    if(tamx <= 50 && tamy <= 50){
		memset(processado,0,sizeof(processado));
    		int total = 0;
    		lo_x = ar;lo_y = ac;
    		hi_x = br;hi_y = bc;
    		for(int i = ar;i<=br;i++){
    			for(int j = ac;j <= bc;j++){
    				if(matriz[i][j] == 1 || processado[i][j]) continue;
    				//printf("Componente nova\n");
    				dfs(i,j);
    				total++;
    			}
    		}
    		return total;
	}
	else{
		node resposta = query(1,1,tamy,ac,bc);
		if(ar == 1 && br == 1){
			return resposta.s0;
		}
		else if(ar == 2 && br == 2){
			return resposta.s1;
		}
		else{
			return resposta.componentes;
		}
	}
}

Compilation message

rainbow.cpp: In member function 'node node::operator+(const node&) const':
rainbow.cpp:32:7: warning: unused variable 'q3' [-Wunused-variable]
   int q3 = q1 || q2;
       ^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 22264 KB Output is correct
2 Correct 28 ms 22264 KB Output is correct
3 Correct 42 ms 22424 KB Output is correct
4 Correct 46 ms 22516 KB Output is correct
5 Correct 27 ms 22516 KB Output is correct
6 Correct 20 ms 22516 KB Output is correct
7 Correct 21 ms 22516 KB Output is correct
8 Correct 22 ms 22516 KB Output is correct
9 Correct 22 ms 22516 KB Output is correct
10 Correct 26 ms 22516 KB Output is correct
11 Correct 44 ms 22608 KB Output is correct
12 Correct 41 ms 22700 KB Output is correct
13 Correct 34 ms 22700 KB Output is correct
14 Correct 29 ms 22700 KB Output is correct
15 Correct 22 ms 22700 KB Output is correct
16 Correct 22 ms 22700 KB Output is correct
17 Correct 19 ms 22700 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 22700 KB Output is correct
2 Correct 19 ms 22700 KB Output is correct
3 Incorrect 199 ms 23632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 22700 KB Output is correct
2 Runtime error 50 ms 44716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 22264 KB Output is correct
2 Correct 28 ms 22264 KB Output is correct
3 Correct 42 ms 22424 KB Output is correct
4 Correct 46 ms 22516 KB Output is correct
5 Correct 27 ms 22516 KB Output is correct
6 Correct 20 ms 22516 KB Output is correct
7 Correct 21 ms 22516 KB Output is correct
8 Correct 22 ms 22516 KB Output is correct
9 Correct 22 ms 22516 KB Output is correct
10 Correct 26 ms 22516 KB Output is correct
11 Correct 44 ms 22608 KB Output is correct
12 Correct 41 ms 22700 KB Output is correct
13 Correct 34 ms 22700 KB Output is correct
14 Correct 29 ms 22700 KB Output is correct
15 Correct 22 ms 22700 KB Output is correct
16 Correct 22 ms 22700 KB Output is correct
17 Correct 19 ms 22700 KB Output is correct
18 Runtime error 54 ms 44900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 22264 KB Output is correct
2 Correct 28 ms 22264 KB Output is correct
3 Correct 42 ms 22424 KB Output is correct
4 Correct 46 ms 22516 KB Output is correct
5 Correct 27 ms 22516 KB Output is correct
6 Correct 20 ms 22516 KB Output is correct
7 Correct 21 ms 22516 KB Output is correct
8 Correct 22 ms 22516 KB Output is correct
9 Correct 22 ms 22516 KB Output is correct
10 Correct 26 ms 22516 KB Output is correct
11 Correct 44 ms 22608 KB Output is correct
12 Correct 41 ms 22700 KB Output is correct
13 Correct 34 ms 22700 KB Output is correct
14 Correct 29 ms 22700 KB Output is correct
15 Correct 22 ms 22700 KB Output is correct
16 Correct 22 ms 22700 KB Output is correct
17 Correct 19 ms 22700 KB Output is correct
18 Runtime error 54 ms 44900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -