oj.uz

답안 #811158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
811158 2023-08-07T01:25:35 Z andecaandeci Tracks in the Snow (BOI13_tracks) C++17
45.3125 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

char grid[4005][4005], cur;
bool vis[4005][4005];
int h, w, n, cnt, ans = 0;

bool valid(int i, int j){
    return (i>=1 && i<=h && j>=1 && j<=w);
}

void dfs(int i, int j){
    cnt++;
    vis[i][j] = 1;
    if(!vis[i+1][j] && valid(i+1,j) && grid[i+1][j]==cur){
        grid[i+1][j] = (cur=='F' ? 'R' : 'F');
        dfs(i+1,j);
    }
    if(!vis[i][j+1] && valid(i,j+1) && grid[i][j+1]==cur){
        grid[i][j+1] = (cur=='F' ? 'R' : 'F');
        dfs(i,j+1);
    }
    if(!vis[i-1][j] && valid(i-1,j) && grid[i-1][j]==cur){
        grid[i-1][j] = (cur=='F' ? 'R' : 'F');
        dfs(i-1,j);
    }
    if(!vis[i][j-1] && valid(i,j-1) && grid[i][j-1]==cur){
        grid[i][j-1] = (cur=='F' ? 'R' : 'F');
        dfs(i,j-1);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>h>>w;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin>>grid[i][j];
            if(grid[i][j] != '.') n++;
        }
    }
    if(grid[1][1] == '.') {
        cout<<"0\n";
        return 0;
    }


    while(cnt<n){
        cnt = 0;
        cur = grid[1][1];
        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++) vis[i][j] = 0;
        }

        grid[1][1] = (cur=='F' ? 'R' : 'F');
        dfs(1,1);
        ++ans;
    }

    cout<<ans<<'\n';

    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 26800 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 26 ms 20904 KB Output is correct
5 Correct 32 ms 3576 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 28 ms 2528 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 49 ms 9932 KB Output is correct
13 Correct 31 ms 3552 KB Output is correct
14 Correct 37 ms 3528 KB Output is correct
15 Correct 245 ms 8428 KB Output is correct
16 Correct 206 ms 26836 KB Output is correct
17 Correct 233 ms 10088 KB Output is correct
18 Correct 27 ms 20948 KB Output is correct

Subtask #2
15.3125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1324 ms 31428 KB Output is correct
2 Execution timed out 2083 ms 14400 KB Time limit exceeded
3 Execution timed out 2076 ms 32548 KB Time limit exceeded
4 Execution timed out 2059 ms 35180 KB Time limit exceeded
5 Execution timed out 2069 ms 24396 KB Time limit exceeded
6 Runtime error 1051 ms 1048576 KB Execution killed with signal 9
7 Correct 1273 ms 32352 KB Output is correct
8 Correct 1449 ms 31416 KB Output is correct
9 Correct 66 ms 2004 KB Output is correct
10 Correct 147 ms 820 KB Output is correct
11 Correct 474 ms 31484 KB Output is correct
12 Correct 964 ms 2704 KB Output is correct
13 Execution timed out 2074 ms 14384 KB Time limit exceeded
14 Execution timed out 2086 ms 10088 KB Time limit exceeded
15 Execution timed out 2072 ms 10024 KB Time limit exceeded
16 Execution timed out 2073 ms 7304 KB Time limit exceeded
17 Execution timed out 2088 ms 18500 KB Time limit exceeded
18 Execution timed out 2078 ms 17304 KB Time limit exceeded
19 Execution timed out 2069 ms 35156 KB Time limit exceeded
20 Execution timed out 2071 ms 14992 KB Time limit exceeded
21 Execution timed out 2052 ms 25268 KB Time limit exceeded
22 Execution timed out 2074 ms 24440 KB Time limit exceeded
23 Execution timed out 2089 ms 21740 KB Time limit exceeded
24 Execution timed out 2047 ms 25280 KB Time limit exceeded
25 Execution timed out 2057 ms 32488 KB Time limit exceeded
26 Runtime error 622 ms 1048576 KB Execution killed with signal 9
27 Runtime error 972 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1004 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1117 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1147 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2088 ms 334044 KB Time limit exceeded
32 Runtime error 645 ms 1048576 KB Execution killed with signal 9