Submission #811577

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
811577	2023-08-07T04:58:56 Z	makanhulia	Tracks in the Snow (BOI13_tracks)	C++17	2.1875 / 100	2000 ms	17396 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	2045 ms	2260 KB	Time limit exceeded
2	Execution timed out	2062 ms	340 KB	Time limit exceeded
3	Execution timed out	2048 ms	468 KB	Time limit exceeded
4	Incorrect	54 ms	2260 KB	Output isn't correct
5	Execution timed out	2078 ms	1364 KB	Time limit exceeded
6	Execution timed out	2079 ms	340 KB	Time limit exceeded
7	Execution timed out	2071 ms	456 KB	Time limit exceeded
8	Incorrect	1 ms	468 KB	Output isn't correct
9	Execution timed out	2074 ms	724 KB	Time limit exceeded
10	Execution timed out	2071 ms	1280 KB	Time limit exceeded
11	Incorrect	4 ms	1108 KB	Output isn't correct
12	Execution timed out	2066 ms	1492 KB	Time limit exceeded
13	Execution timed out	2070 ms	1492 KB	Time limit exceeded
14	Execution timed out	2075 ms	1492 KB	Time limit exceeded
15	Execution timed out	2069 ms	2376 KB	Time limit exceeded
16	Execution timed out	2067 ms	2388 KB	Time limit exceeded
17	Execution timed out	2077 ms	2260 KB	Time limit exceeded
18	Incorrect	55 ms	2388 KB	Output isn't correct

Subtask #2

2.1875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2070 ms	15568 KB	Time limit exceeded
2	Execution timed out	2029 ms	5460 KB	Time limit exceeded
3	Execution timed out	2013 ms	16804 KB	Time limit exceeded
4	Execution timed out	2069 ms	8000 KB	Time limit exceeded
5	Execution timed out	2024 ms	12752 KB	Time limit exceeded
6	Execution timed out	2092 ms	17376 KB	Time limit exceeded
7	Execution timed out	2075 ms	16160 KB	Time limit exceeded
8	Execution timed out	2035 ms	15444 KB	Time limit exceeded
9	Execution timed out	2041 ms	340 KB	Time limit exceeded
10	Execution timed out	2077 ms	340 KB	Time limit exceeded
11	Execution timed out	2083 ms	15828 KB	Time limit exceeded
12	Execution timed out	2084 ms	852 KB	Time limit exceeded
13	Execution timed out	2087 ms	5268 KB	Time limit exceeded
14	Execution timed out	2076 ms	3836 KB	Time limit exceeded
15	Execution timed out	2028 ms	4180 KB	Time limit exceeded
16	Execution timed out	2069 ms	1876 KB	Time limit exceeded
17	Execution timed out	2055 ms	8208 KB	Time limit exceeded
18	Execution timed out	2061 ms	8192 KB	Time limit exceeded
19	Execution timed out	2070 ms	7692 KB	Time limit exceeded
20	Execution timed out	2069 ms	7308 KB	Time limit exceeded
21	Execution timed out	2081 ms	12588 KB	Time limit exceeded
22	Execution timed out	2085 ms	12288 KB	Time limit exceeded
23	Execution timed out	2085 ms	10236 KB	Time limit exceeded
24	Execution timed out	2067 ms	12672 KB	Time limit exceeded
25	Execution timed out	2065 ms	16224 KB	Time limit exceeded
26	Correct	160 ms	15220 KB	Output is correct
27	Incorrect	611 ms	17396 KB	Output isn't correct
28	Execution timed out	2029 ms	17352 KB	Time limit exceeded
29	Execution timed out	2025 ms	17320 KB	Time limit exceeded
30	Execution timed out	2086 ms	16844 KB	Time limit exceeded
31	Execution timed out	2073 ms	13072 KB	Time limit exceeded
32	Execution timed out	2013 ms	17328 KB	Time limit exceeded