oj.uz

답안 #1063733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063733 2024-08-18T00:31:28 Z danielzhu Tracks in the Snow (BOI13_tracks) C++17
91.25 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
int H, W;
int grid[4001][4001], cc[4001][4001];
queue<pair<int,int>> q;
vector<pair<int,int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 
void ff(int cur, int val){
	while(!q.empty()){
		auto temp = q.front();
		int x = temp.first, y = temp.second;
		q.pop();
		for(auto [dx, dy] : dir){
			if((x+dx > -1)&& (x+dx < H) && (y+dy > -1) && (y+dy < W) && (cc[x+dx][y+dy] == -1) && (grid[x+dx][y+dy] == cur)){
				cc[x+dx][y+dy] = val;
				q.push({x+dx, y+dy});
			}
		}
	}
}				
 
int main(){
	cin>>H>>W;
	memset(grid, 0, sizeof(grid));
	memset(cc, -1, sizeof(cc));
	for(int i = 0; i < H; i++){
		string s; cin>>s;
		for(int j = 0; j < W; j++){
			if(s[j] == 'F') grid[i][j] = 1;
			else if(s[j] == 'R') grid[i][j] = 2;
		}
	}
	int val = 0;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(cc[i][j] == -1 && grid[i][j] != 0){
				cc[i][j] = val;
				q.push({i,j});
				ff(grid[i][j], val);
				val++;
			}
		}
	}
	vector<unordered_set<int>> adj(val+1); 
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(grid[i][j] != 0){
				for(auto [dx, dy] : dir){
					if(i+dx > -1 && i+dx < H && j+dy > -1 && j+dy < W && cc[i+dx][j+dy] != cc[i][j] && cc[i+dx][j+dy] != -1){
						adj[cc[i][j]].insert(cc[i+dx][j+dy]);
						adj[cc[i+dx][j+dy]].insert(cc[i][j]);
					}
				}
			}
		}
	}
	queue<int> q1;
	q1.push(0);
	vector<int> d(val+1, -1);
	int ans = 0;
	d[0] = 0;
	while(!q1.empty()){
		auto temp = q1.front();
		q1.pop();
		for(auto i : adj[temp]){
			if(d[i] == -1){
				q1.push(i);
				d[i] = d[temp] + 1;
				ans = max(ans, d[i]);
			}
		}
	}
	cout<<ans+1<<endl;
	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 134740 KB Output is correct
2 Correct 46 ms 125528 KB Output is correct
3 Correct 46 ms 125572 KB Output is correct
4 Correct 61 ms 126288 KB Output is correct
5 Correct 62 ms 127572 KB Output is correct
6 Correct 45 ms 125788 KB Output is correct
7 Correct 45 ms 125764 KB Output is correct
8 Correct 50 ms 125776 KB Output is correct
9 Correct 47 ms 125776 KB Output is correct
10 Correct 57 ms 127576 KB Output is correct
11 Correct 53 ms 125780 KB Output is correct
12 Correct 60 ms 129104 KB Output is correct
13 Correct 51 ms 127568 KB Output is correct
14 Correct 55 ms 127572 KB Output is correct
15 Correct 95 ms 134744 KB Output is correct
16 Correct 104 ms 134992 KB Output is correct
17 Correct 74 ms 134224 KB Output is correct
18 Correct 54 ms 126288 KB Output is correct

Subtask #2
61.25 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 126804 KB Output is correct
2 Correct 205 ms 173140 KB Output is correct
3 Correct 919 ms 467236 KB Output is correct
4 Correct 294 ms 185428 KB Output is correct
5 Runtime error 1455 ms 1048576 KB Execution killed with signal 9
6 Correct 1333 ms 258392 KB Output is correct
7 Correct 53 ms 126544 KB Output is correct
8 Correct 54 ms 126800 KB Output is correct
9 Correct 60 ms 127056 KB Output is correct
10 Correct 51 ms 126192 KB Output is correct
11 Correct 54 ms 126108 KB Output is correct
12 Correct 50 ms 128088 KB Output is correct
13 Correct 183 ms 173016 KB Output is correct
14 Correct 133 ms 153424 KB Output is correct
15 Correct 170 ms 158544 KB Output is correct
16 Correct 118 ms 147536 KB Output is correct
17 Correct 429 ms 249340 KB Output is correct
18 Correct 507 ms 252756 KB Output is correct
19 Correct 284 ms 185296 KB Output is correct
20 Correct 244 ms 203288 KB Output is correct
21 Correct 606 ms 329812 KB Output is correct
22 Runtime error 1228 ms 1048576 KB Execution killed with signal 9
23 Correct 794 ms 364312 KB Output is correct
24 Correct 906 ms 471272 KB Output is correct
25 Execution timed out 2021 ms 651524 KB Time limit exceeded
26 Correct 549 ms 125524 KB Output is correct
27 Correct 678 ms 129576 KB Output is correct
28 Correct 1397 ms 258468 KB Output is correct
29 Correct 1105 ms 205072 KB Output is correct
30 Correct 967 ms 181912 KB Output is correct
31 Execution timed out 2064 ms 506140 KB Time limit exceeded
32 Correct 684 ms 157396 KB Output is correct