oj.uz

답안 #1063720

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063720 2024-08-18T00:14:13 Z danielzhu Tracks in the Snow (BOI13_tracks) C++17
95.625 / 100
 1957 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 && grid[i+dx][j+dy] != grid[i][j] && grid[i+dx][j+dy] != 0){
						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 79 ms 134992 KB Output is correct
2 Correct 45 ms 125524 KB Output is correct
3 Correct 45 ms 125780 KB Output is correct
4 Correct 59 ms 126292 KB Output is correct
5 Correct 52 ms 127572 KB Output is correct
6 Correct 44 ms 125512 KB Output is correct
7 Correct 44 ms 125780 KB Output is correct
8 Correct 47 ms 125780 KB Output is correct
9 Correct 50 ms 125788 KB Output is correct
10 Correct 51 ms 127568 KB Output is correct
11 Correct 51 ms 125856 KB Output is correct
12 Correct 60 ms 129120 KB Output is correct
13 Correct 61 ms 127508 KB Output is correct
14 Correct 56 ms 127572 KB Output is correct
15 Correct 77 ms 134932 KB Output is correct
16 Correct 89 ms 134992 KB Output is correct
17 Correct 71 ms 134224 KB Output is correct
18 Correct 54 ms 126288 KB Output is correct

Subtask #2
65.625 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 126804 KB Output is correct
2 Correct 196 ms 173956 KB Output is correct
3 Correct 802 ms 472916 KB Output is correct
4 Correct 253 ms 186192 KB Output is correct
5 Runtime error 1441 ms 1048576 KB Execution killed with signal 9
6 Correct 1277 ms 260476 KB Output is correct
7 Correct 49 ms 126552 KB Output is correct
8 Correct 54 ms 126800 KB Output is correct
9 Correct 53 ms 127272 KB Output is correct
10 Correct 47 ms 126288 KB Output is correct
11 Correct 50 ms 126036 KB Output is correct
12 Correct 54 ms 128084 KB Output is correct
13 Correct 170 ms 173848 KB Output is correct
14 Correct 118 ms 153944 KB Output is correct
15 Correct 139 ms 159180 KB Output is correct
16 Correct 108 ms 148048 KB Output is correct
17 Correct 356 ms 251476 KB Output is correct
18 Correct 442 ms 255056 KB Output is correct
19 Correct 259 ms 186196 KB Output is correct
20 Correct 260 ms 204532 KB Output is correct
21 Correct 638 ms 333136 KB Output is correct
22 Runtime error 916 ms 1048576 KB Execution killed with signal 9
23 Correct 678 ms 368212 KB Output is correct
24 Correct 805 ms 477016 KB Output is correct
25 Correct 1853 ms 660564 KB Output is correct
26 Correct 528 ms 125524 KB Output is correct
27 Correct 696 ms 129616 KB Output is correct
28 Correct 1331 ms 260476 KB Output is correct
29 Correct 1148 ms 206320 KB Output is correct
30 Correct 962 ms 182728 KB Output is correct
31 Correct 1957 ms 511272 KB Output is correct
32 Correct 704 ms 157868 KB Output is correct