oj.uz

답안 #1032544

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032544 2024-07-24T01:53:24 Z hippo123 Tracks in the Snow (BOI13_tracks) C++17
56.25 / 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));
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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