oj.uz

답안 #811274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
811274 2023-08-07T03:36:22 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 187 ms 27012 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 24 ms 21108 KB Output is correct
5 Correct 31 ms 3688 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 26 ms 2556 KB Output is correct
11 Correct 5 ms 6220 KB Output is correct
12 Correct 36 ms 9960 KB Output is correct
13 Correct 31 ms 3660 KB Output is correct
14 Correct 31 ms 3620 KB Output is correct
15 Correct 234 ms 8788 KB Output is correct
16 Correct 182 ms 27040 KB Output is correct
17 Correct 220 ms 10324 KB Output is correct
18 Correct 24 ms 21048 KB Output is correct

Subtask #2
15.3125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1289 ms 31460 KB Output is correct
2 Execution timed out 2062 ms 15628 KB Time limit exceeded
3 Execution timed out 2068 ms 35572 KB Time limit exceeded
4 Execution timed out 2066 ms 37184 KB Time limit exceeded
5 Execution timed out 2098 ms 27564 KB Time limit exceeded
6 Runtime error 1173 ms 1048576 KB Execution killed with signal 9
7 Correct 1301 ms 32352 KB Output is correct
8 Correct 1489 ms 31452 KB Output is correct
9 Correct 67 ms 2004 KB Output is correct
10 Correct 143 ms 948 KB Output is correct
11 Correct 563 ms 31532 KB Output is correct
12 Correct 1022 ms 2652 KB Output is correct
13 Execution timed out 2069 ms 15940 KB Time limit exceeded
14 Execution timed out 2080 ms 10740 KB Time limit exceeded
15 Execution timed out 2070 ms 11012 KB Time limit exceeded
16 Execution timed out 2049 ms 7836 KB Time limit exceeded
17 Execution timed out 2091 ms 21196 KB Time limit exceeded
18 Execution timed out 2023 ms 19920 KB Time limit exceeded
19 Execution timed out 2065 ms 38396 KB Time limit exceeded
20 Execution timed out 2077 ms 18344 KB Time limit exceeded
21 Execution timed out 2080 ms 31748 KB Time limit exceeded
22 Execution timed out 2102 ms 30944 KB Time limit exceeded
23 Execution timed out 2011 ms 27676 KB Time limit exceeded
24 Execution timed out 2009 ms 31840 KB Time limit exceeded
25 Execution timed out 2096 ms 38988 KB Time limit exceeded
26 Runtime error 665 ms 1048576 KB Execution killed with signal 9
27 Runtime error 987 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1026 ms 1048576 KB Execution killed with signal 9
29 Runtime error 978 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1163 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2109 ms 342876 KB Time limit exceeded
32 Runtime error 698 ms 1048576 KB Execution killed with signal 9