oj.uz

답안 #1063730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063730 2024-08-18T00:27:35 Z danielzhu Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 2000 ms 781012 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> d(val+1, -1);
	int ans = 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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 132612 KB Output isn't correct
2 Incorrect 53 ms 125528 KB Output isn't correct
3 Incorrect 45 ms 125788 KB Output isn't correct
4 Incorrect 55 ms 126032 KB Output isn't correct
5 Incorrect 57 ms 126800 KB Output isn't correct
6 Incorrect 45 ms 125520 KB Output isn't correct
7 Incorrect 45 ms 125532 KB Output isn't correct
8 Incorrect 48 ms 125788 KB Output isn't correct
9 Incorrect 44 ms 125776 KB Output isn't correct
10 Incorrect 55 ms 126904 KB Output isn't correct
11 Incorrect 53 ms 125768 KB Output isn't correct
12 Incorrect 64 ms 128140 KB Output isn't correct
13 Incorrect 65 ms 126768 KB Output isn't correct
14 Incorrect 48 ms 126804 KB Output isn't correct
15 Incorrect 79 ms 132176 KB Output isn't correct
16 Incorrect 95 ms 132452 KB Output isn't correct
17 Incorrect 68 ms 131664 KB Output isn't correct
18 Incorrect 59 ms 126032 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 126288 KB Output isn't correct
2 Incorrect 162 ms 157456 KB Output isn't correct
3 Incorrect 729 ms 347940 KB Output isn't correct
4 Incorrect 217 ms 164784 KB Output isn't correct
5 Incorrect 820 ms 776224 KB Output isn't correct
6 Incorrect 1635 ms 207140 KB Output isn't correct
7 Incorrect 56 ms 126348 KB Output isn't correct
8 Incorrect 59 ms 126292 KB Output isn't correct
9 Incorrect 58 ms 126700 KB Output isn't correct
10 Incorrect 59 ms 126036 KB Output isn't correct
11 Incorrect 57 ms 125880 KB Output isn't correct
12 Incorrect 62 ms 127292 KB Output isn't correct
13 Incorrect 179 ms 158548 KB Output isn't correct
14 Incorrect 122 ms 145004 KB Output isn't correct
15 Incorrect 121 ms 146904 KB Output isn't correct
16 Incorrect 139 ms 141140 KB Output isn't correct
17 Incorrect 350 ms 210684 KB Output isn't correct
18 Incorrect 326 ms 207696 KB Output isn't correct
19 Incorrect 291 ms 166996 KB Output isn't correct
20 Incorrect 214 ms 178324 KB Output isn't correct
21 Incorrect 461 ms 263748 KB Output isn't correct
22 Incorrect 876 ms 781012 KB Output isn't correct
23 Incorrect 665 ms 290192 KB Output isn't correct
24 Incorrect 501 ms 347352 KB Output isn't correct
25 Incorrect 1383 ms 463956 KB Output isn't correct
26 Correct 518 ms 131920 KB Output is correct
27 Incorrect 755 ms 136504 KB Output isn't correct
28 Incorrect 1716 ms 215584 KB Output isn't correct
29 Incorrect 1500 ms 181988 KB Output isn't correct
30 Incorrect 1212 ms 168116 KB Output isn't correct
31 Execution timed out 2027 ms 416804 KB Time limit exceeded
32 Incorrect 701 ms 153980 KB Output isn't correct