Submission #811128

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
811128	2023-08-07T00:52:51 Z	makanhulia	Tracks in the Snow (BOI13_tracks)	C++17	2.1875 / 100	2000 ms	16232 KB

tracks

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

char grid[4005][4005], cur;
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++;
    if(valid(i+1,j) && grid[i+1][j]==cur){
        grid[i+1][j] = (cur=='F' ? 'R' : 'F');
        dfs(i+1,j);
    }
    if(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];
        grid[1][1] = (cur=='F' ? 'R' : 'F');
        dfs(1,1);
        ++ans;
    }

    cout<<ans<<'\n';

    return 0;
}

Subtask #1

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2069 ms	2260 KB	Time limit exceeded
2	Execution timed out	2070 ms	340 KB	Time limit exceeded
3	Execution timed out	2075 ms	468 KB	Time limit exceeded
4	Incorrect	54 ms	2260 KB	Output isn't correct
5	Execution timed out	2081 ms	1364 KB	Time limit exceeded
6	Execution timed out	2075 ms	340 KB	Time limit exceeded
7	Execution timed out	2044 ms	468 KB	Time limit exceeded
8	Incorrect	1 ms	468 KB	Output isn't correct
9	Execution timed out	2063 ms	596 KB	Time limit exceeded
10	Execution timed out	2072 ms	1236 KB	Time limit exceeded
11	Incorrect	4 ms	1108 KB	Output isn't correct
12	Execution timed out	2084 ms	1364 KB	Time limit exceeded
13	Execution timed out	2084 ms	1364 KB	Time limit exceeded
14	Execution timed out	2088 ms	1364 KB	Time limit exceeded
15	Execution timed out	2087 ms	2260 KB	Time limit exceeded
16	Execution timed out	2085 ms	2260 KB	Time limit exceeded
17	Execution timed out	2088 ms	2132 KB	Time limit exceeded
18	Incorrect	54 ms	2260 KB	Output isn't correct

Subtask #2

2.1875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2076 ms	15444 KB	Time limit exceeded
2	Execution timed out	2067 ms	5204 KB	Time limit exceeded
3	Execution timed out	2074 ms	16128 KB	Time limit exceeded
4	Execution timed out	2077 ms	7756 KB	Time limit exceeded
5	Execution timed out	2071 ms	12236 KB	Time limit exceeded
6	Execution timed out	2073 ms	16112 KB	Time limit exceeded
7	Execution timed out	2066 ms	16212 KB	Time limit exceeded
8	Execution timed out	2076 ms	15444 KB	Time limit exceeded
9	Execution timed out	2066 ms	340 KB	Time limit exceeded
10	Execution timed out	2068 ms	340 KB	Time limit exceeded
11	Execution timed out	2070 ms	15884 KB	Time limit exceeded
12	Execution timed out	2075 ms	852 KB	Time limit exceeded
13	Execution timed out	2062 ms	5204 KB	Time limit exceeded
14	Execution timed out	2056 ms	3924 KB	Time limit exceeded
15	Execution timed out	2074 ms	4228 KB	Time limit exceeded
16	Execution timed out	2067 ms	1876 KB	Time limit exceeded
17	Execution timed out	2067 ms	8268 KB	Time limit exceeded
18	Execution timed out	2070 ms	8260 KB	Time limit exceeded
19	Execution timed out	2065 ms	7676 KB	Time limit exceeded
20	Execution timed out	2080 ms	7276 KB	Time limit exceeded
21	Execution timed out	2081 ms	12564 KB	Time limit exceeded
22	Execution timed out	2086 ms	12232 KB	Time limit exceeded
23	Execution timed out	2070 ms	10188 KB	Time limit exceeded
24	Execution timed out	2087 ms	12684 KB	Time limit exceeded
25	Execution timed out	2073 ms	16216 KB	Time limit exceeded
26	Correct	150 ms	14156 KB	Output is correct
27	Incorrect	619 ms	16224 KB	Output isn't correct
28	Execution timed out	2085 ms	16228 KB	Time limit exceeded
29	Execution timed out	2086 ms	16232 KB	Time limit exceeded
30	Execution timed out	2063 ms	15860 KB	Time limit exceeded
31	Execution timed out	2088 ms	13004 KB	Time limit exceeded
32	Execution timed out	2079 ms	16108 KB	Time limit exceeded