oj.uz

답안 #1063702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063702 2024-08-17T23:52:38 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 && 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 = INT_MIN;
	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 91 ms 135024 KB Output is correct
2 Correct 51 ms 125524 KB Output is correct
3 Correct 49 ms 125780 KB Output is correct
4 Correct 59 ms 126248 KB Output is correct
5 Correct 50 ms 127572 KB Output is correct
6 Correct 49 ms 125512 KB Output is correct
7 Correct 46 ms 125780 KB Output is correct
8 Correct 44 ms 125780 KB Output is correct
9 Correct 44 ms 125776 KB Output is correct
10 Correct 49 ms 127568 KB Output is correct
11 Correct 55 ms 125780 KB Output is correct
12 Correct 59 ms 129040 KB Output is correct
13 Correct 53 ms 127604 KB Output is correct
14 Correct 50 ms 127572 KB Output is correct
15 Correct 79 ms 134992 KB Output is correct
16 Correct 93 ms 135080 KB Output is correct
17 Correct 74 ms 134228 KB Output is correct
18 Correct 53 ms 126288 KB Output is correct

Subtask #2
61.25 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 126800 KB Output is correct
2 Correct 168 ms 173920 KB Output is correct
3 Correct 826 ms 472916 KB Output is correct
4 Correct 308 ms 186192 KB Output is correct
5 Runtime error 1516 ms 1048576 KB Execution killed with signal 9
6 Correct 1256 ms 260476 KB Output is correct
7 Correct 49 ms 126548 KB Output is correct
8 Correct 51 ms 126872 KB Output is correct
9 Correct 55 ms 127316 KB Output is correct
10 Correct 55 ms 126340 KB Output is correct
11 Correct 52 ms 126036 KB Output is correct
12 Correct 48 ms 128252 KB Output is correct
13 Correct 197 ms 173904 KB Output is correct
14 Correct 152 ms 153680 KB Output is correct
15 Correct 157 ms 159060 KB Output is correct
16 Correct 114 ms 148048 KB Output is correct
17 Correct 378 ms 251476 KB Output is correct
18 Correct 523 ms 254976 KB Output is correct
19 Correct 232 ms 186452 KB Output is correct
20 Correct 298 ms 204672 KB Output is correct
21 Correct 501 ms 333136 KB Output is correct
22 Runtime error 959 ms 1048576 KB Execution killed with signal 9
23 Correct 669 ms 368208 KB Output is correct
24 Correct 596 ms 477008 KB Output is correct
25 Correct 1824 ms 660560 KB Output is correct
26 Incorrect 510 ms 125744 KB Output isn't correct
27 Correct 664 ms 129616 KB Output is correct
28 Correct 1334 ms 260436 KB Output is correct
29 Correct 1073 ms 206272 KB Output is correct
30 Correct 915 ms 182724 KB Output is correct
31 Execution timed out 2045 ms 511312 KB Time limit exceeded
32 Correct 647 ms 157868 KB Output is correct