Submission #1032544

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1032544	2024-07-24T01:53:24 Z	hippo123	Tracks in the Snow (BOI13_tracks)	C++17	56.25 / 100	2000 ms	1048576 KB

tracks

#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));
map<pr, int> ms; 
vector<vector<bool>> vis(ndim, vector<bool>(ndim, false));
vector<set<int>> adj(2e5);



int h, w; 



	int dx[4]={1, -1, 0, 0}; 
	int dy[4]={0, 0, 1, -1};

void dfs(int x, int y, int col, int num){
	if(x<0 || x>=h || y<0 || y>=w ) return; 
	if(d[x][y]!=col || vis[x][y]) return;
	
	//cout<<" x/y= "<<x<<" "<<y<<endl;
	
	ms[{x,y}]=num; 
	vis[x][y]=true;
	
	for (int i=0; i<4; i++){
		int xn=x+dx[i]; int yn=y+dy[i]; 
		dfs(xn, yn, col, num);
	} 
}

void dfs1(int x, int y, int col, int num){
	if(x<0 || x>=h || y<0 || y>=w ) return; 
	if(d[x][y]!=col || vis[x][y]) return;
	
	//cout<<" x/y= "<<x<<" "<<y<<endl;
	vis[x][y]=true;
	
	for (int i=0; i<4; i++){
		
		int xn=x+dx[i]; int yn=y+dy[i]; 
		if(xn<0 || xn>=h || yn<0 || yn>=w ) continue;
		if(d[xn][yn]==-1) continue; 
		if(d[xn][yn]!=d[x][y]){
			adj[ms[{xn, yn}]].insert(ms[{x, y}]);
			adj[ms[{x, y}]].insert(ms[{xn, yn}]);
		}
		
		dfs1(xn, yn, col, num);
	} 
}

int main(){
	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;
	//}
	int num=0;
	for (int i=0; i<h; i++){
		for (int j=0; j<w; j++){
			if((d[i][j]!=-1) & (!vis[i][j])) {
				dfs(i, j, d[i][j], num); 
				num++;
			}
		}
	}
	//cout<<" we are here"<<endl;
	//==============
	for (int i=0; i<h; i++){
		for (int j=0; j<w; j++) vis[i][j]=false;
	}
	
	for (int i=0; i<h; i++){
		for (int j=0; j<w; j++){
			if((d[i][j]!=-1) & (!vis[i][j])) {
				dfs1(i, j, d[i][j], num); 
			}
		}
	}
	//cout<<" we are here"<<endl;
	
	//for (int i=0; i<num; i++) {
	//	for (auto e: adj[i]) cout<<e<<" ";
	//	cout<<endl;
	//}
	
	
	vector<bool> vis1(num, false);
	vector<int> level(num, -1);
	queue<pr> q; q.push({0, 0}); // node, lev
	level[0]=0;
	int lv_max=0;
	while (!q.empty()){
		pr nd=q.front(); q.pop();
		int node=nd.f; int lev=nd.s;
		for (int elem: adj[node]){
			//cout<<" elem= "<<elem<<endl;
			if(level[elem]==-1){
				level[elem]=lev+1; q.push({elem, lev+1}); 				
				lv_max=max(lv_max, lev+1);
			}
		}
	}
	cout<<lv_max+1<<endl;
	
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	235 ms	95136 KB	Output is correct
2	Correct	37 ms	74576 KB	Output is correct
3	Correct	40 ms	74836 KB	Output is correct
4	Correct	101 ms	86868 KB	Output is correct
5	Correct	50 ms	77136 KB	Output is correct
6	Correct	33 ms	74576 KB	Output is correct
7	Correct	36 ms	74788 KB	Output is correct
8	Correct	39 ms	75088 KB	Output is correct
9	Correct	36 ms	74840 KB	Output is correct
10	Correct	53 ms	77396 KB	Output is correct
11	Correct	53 ms	78160 KB	Output is correct
12	Correct	94 ms	81996 KB	Output is correct
13	Correct	48 ms	77036 KB	Output is correct
14	Correct	48 ms	76884 KB	Output is correct
15	Correct	176 ms	91216 KB	Output is correct
16	Correct	230 ms	95312 KB	Output is correct
17	Correct	112 ms	86352 KB	Output is correct
18	Correct	104 ms	86864 KB	Output is correct

Subtask #2

26.25 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	76888 KB	Output is correct
2	Correct	495 ms	140376 KB	Output is correct
3	Runtime error	1303 ms	697492 KB	Execution killed with signal 11
4	Runtime error	276 ms	229464 KB	Execution killed with signal 11
5	Runtime error	1000 ms	733792 KB	Execution killed with signal 11
6	Execution timed out	2076 ms	696572 KB	Time limit exceeded
7	Correct	43 ms	76628 KB	Output is correct
8	Correct	41 ms	76884 KB	Output is correct
9	Correct	51 ms	78416 KB	Output is correct
10	Correct	40 ms	76272 KB	Output is correct
11	Correct	39 ms	76108 KB	Output is correct
12	Correct	44 ms	76624 KB	Output is correct
13	Correct	482 ms	140372 KB	Output is correct
14	Correct	298 ms	112980 KB	Output is correct
15	Correct	225 ms	107836 KB	Output is correct
16	Correct	286 ms	108832 KB	Output is correct
17	Runtime error	449 ms	366420 KB	Execution killed with signal 11
18	Runtime error	364 ms	297208 KB	Execution killed with signal 11
19	Runtime error	277 ms	229548 KB	Execution killed with signal 11
20	Runtime error	508 ms	311732 KB	Execution killed with signal 11
21	Runtime error	841 ms	494316 KB	Execution killed with signal 11
22	Runtime error	1012 ms	733460 KB	Execution killed with signal 11
23	Runtime error	788 ms	573268 KB	Execution killed with signal 11
24	Runtime error	893 ms	581716 KB	Execution killed with signal 11
25	Runtime error	1454 ms	786352 KB	Execution killed with signal 11
26	Runtime error	1558 ms	1048576 KB	Execution killed with signal 9
27	Execution timed out	2059 ms	1003716 KB	Time limit exceeded
28	Execution timed out	2097 ms	705364 KB	Time limit exceeded
29	Execution timed out	2058 ms	683528 KB	Time limit exceeded
30	Execution timed out	2111 ms	745040 KB	Time limit exceeded
31	Execution timed out	2131 ms	769032 KB	Time limit exceeded
32	Execution timed out	2077 ms	781460 KB	Time limit exceeded