oj.uz

Submission #1032534

# Submission time Handle Problem Language Result Execution time Memory
1032534 2024-07-24T00:25:33 Z hippo123 Tracks in the Snow (BOI13_tracks) C++17
49.6875 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define pr pair<ll, ll>
#define f first
#define s second
#define pb push_back
const int ndim=4001;
int ns;
vector<vector<int>> d(ndim, vector<int>(ndim));

void floodfill(int x, int y, int h, int w, int col){
	// out of bound
	// count & change color
	ns++; d[x][y]^=1;
	
	if(x==h-1 && y==w-1) return; 
	
	
	int dx[4]={1, -1, 0, 0};
	int dy[4]={0, 0, 1, -1};
	
	for (int i=0; i<4; i++){
		int x1=x+dx[i]; int y1=y+dy[i];
		
		if(x1>=0 && x1<h && y1>=0 && y1<w){
			if(d[x1][y1]==col) {
				floodfill(x1, y1, h, w, col); 
			}
		}	
	}
	
}

int main(){
	int h, w; cin>>h>>w;
	//vector<vector<int>> d(h, vector<int> (w, -1));
	int nf=0;
	for (int i=0; i<h; i++){
		string s; cin>>s;
		for (int j=0; j<w; j++){
			if(s[j]=='.') {
				d[i][j]=-1; continue;
			} 
			nf++;
			if(s[j]=='R') d[i][j]=0;
			else d[i][j]=1; 
		}
	}

	//for (int i=0; i<h; i++){
	//	for (int j=0; j<w; j++) cout<<d[i][j]<<" ";
	//	cout<<endl;
	//}
	
	
	ns=0;
	int cnt=0; 
	while(ns<nf){
		ns=0; cnt++; 
		floodfill(0, 0, h, w, d[0][0]);		
		
		if(ns==nf) break;
	}
	cout<<cnt<<endl;
	
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 84376 KB Output is correct
2 Correct 32 ms 63060 KB Output is correct
3 Correct 30 ms 63060 KB Output is correct
4 Correct 48 ms 79956 KB Output is correct
5 Correct 69 ms 64084 KB Output is correct
6 Correct 39 ms 63016 KB Output is correct
7 Correct 35 ms 63060 KB Output is correct
8 Correct 31 ms 63524 KB Output is correct
9 Correct 31 ms 63056 KB Output is correct
10 Correct 58 ms 63656 KB Output is correct
11 Correct 34 ms 67408 KB Output is correct
12 Correct 58 ms 69692 KB Output is correct
13 Correct 56 ms 64092 KB Output is correct
14 Correct 57 ms 64092 KB Output is correct
15 Correct 199 ms 66288 KB Output is correct
16 Correct 135 ms 84600 KB Output is correct
17 Correct 221 ms 67984 KB Output is correct
18 Correct 48 ms 80104 KB Output is correct

Subtask #2
19.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 64812 KB Output is correct
2 Execution timed out 2044 ms 73552 KB Time limit exceeded
3 Execution timed out 2072 ms 80932 KB Time limit exceeded
4 Execution timed out 2070 ms 85424 KB Time limit exceeded
5 Execution timed out 2064 ms 74068 KB Time limit exceeded
6 Runtime error 1582 ms 1048576 KB Execution killed with signal 9
7 Correct 561 ms 64096 KB Output is correct
8 Correct 759 ms 64592 KB Output is correct
9 Correct 106 ms 64596 KB Output is correct
10 Correct 174 ms 63692 KB Output is correct
11 Correct 230 ms 63568 KB Output is correct
12 Correct 634 ms 64440 KB Output is correct
13 Execution timed out 2074 ms 73556 KB Time limit exceeded
14 Correct 1861 ms 68432 KB Output is correct
15 Execution timed out 2061 ms 66984 KB Time limit exceeded
16 Correct 1990 ms 68180 KB Output is correct
17 Execution timed out 2039 ms 74496 KB Time limit exceeded
18 Execution timed out 2025 ms 69388 KB Time limit exceeded
19 Execution timed out 2071 ms 85588 KB Time limit exceeded
20 Execution timed out 2062 ms 68904 KB Time limit exceeded
21 Execution timed out 2072 ms 74356 KB Time limit exceeded
22 Execution timed out 2037 ms 74016 KB Time limit exceeded
23 Execution timed out 2062 ms 77412 KB Time limit exceeded
24 Execution timed out 2070 ms 74872 KB Time limit exceeded
25 Execution timed out 2074 ms 81236 KB Time limit exceeded
26 Runtime error 648 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1225 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1483 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1465 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1246 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2067 ms 308820 KB Time limit exceeded
32 Execution timed out 2073 ms 931272 KB Time limit exceeded