oj.uz

답안 #1063727

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063727 2024-08-18T00:23:35 Z danielzhu Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 2000 ms 793928 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<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> v(val+1, 0), d(val+1, 0);
	v[0] = 1;
	int ans = 0;
	while(!q1.empty()){
		auto temp = q1.front();
		q1.pop();
		for(auto i : adj[temp]){
			if(!v[i]){
				q1.push(i);
				v[i] = 1;
				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 102 ms 132692 KB Output is correct
2 Correct 45 ms 125532 KB Output is correct
3 Correct 45 ms 125524 KB Output is correct
4 Correct 56 ms 126036 KB Output is correct
5 Correct 48 ms 126804 KB Output is correct
6 Correct 45 ms 125708 KB Output is correct
7 Correct 50 ms 125776 KB Output is correct
8 Correct 47 ms 125524 KB Output is correct
9 Correct 53 ms 125784 KB Output is correct
10 Correct 65 ms 126960 KB Output is correct
11 Correct 48 ms 125668 KB Output is correct
12 Correct 74 ms 128288 KB Output is correct
13 Correct 49 ms 126800 KB Output is correct
14 Correct 59 ms 126800 KB Output is correct
15 Correct 77 ms 132176 KB Output is correct
16 Correct 90 ms 132688 KB Output is correct
17 Correct 66 ms 131664 KB Output is correct
18 Correct 56 ms 126036 KB Output is correct

Subtask #2
67.8125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 126288 KB Output is correct
2 Correct 167 ms 158288 KB Output is correct
3 Correct 729 ms 353488 KB Output is correct
4 Correct 234 ms 165712 KB Output is correct
5 Correct 819 ms 793928 KB Output is correct
6 Correct 1583 ms 209232 KB Output is correct
7 Correct 49 ms 126288 KB Output is correct
8 Correct 51 ms 126288 KB Output is correct
9 Correct 48 ms 126804 KB Output is correct
10 Correct 50 ms 125996 KB Output is correct
11 Correct 46 ms 126004 KB Output is correct
12 Correct 46 ms 127156 KB Output is correct
13 Correct 160 ms 158396 KB Output is correct
14 Correct 110 ms 144720 KB Output is correct
15 Correct 107 ms 146772 KB Output is correct
16 Correct 104 ms 141136 KB Output is correct
17 Correct 352 ms 210520 KB Output is correct
18 Correct 347 ms 207532 KB Output is correct
19 Correct 212 ms 165672 KB Output is correct
20 Correct 195 ms 177744 KB Output is correct
21 Correct 432 ms 261968 KB Output is correct
22 Correct 888 ms 793888 KB Output is correct
23 Correct 718 ms 289620 KB Output is correct
24 Correct 479 ms 348244 KB Output is correct
25 Correct 1372 ms 464468 KB Output is correct
26 Correct 517 ms 125524 KB Output is correct
27 Correct 685 ms 128084 KB Output is correct
28 Correct 1596 ms 209232 KB Output is correct
29 Correct 1518 ms 174932 KB Output is correct
30 Correct 1240 ms 160552 KB Output is correct
31 Execution timed out 2044 ms 416540 KB Time limit exceeded
32 Correct 682 ms 146000 KB Output is correct