Submission #811220

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
811220	2023-08-07T02:38:41 Z	makanhulia	Tracks in the Snow (BOI13_tracks)	C++17	2.1875 / 100	2000 ms	16596 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	2058 ms	2260 KB	Time limit exceeded
2	Execution timed out	2063 ms	340 KB	Time limit exceeded
3	Execution timed out	2032 ms	468 KB	Time limit exceeded
4	Incorrect	54 ms	2260 KB	Output isn't correct
5	Execution timed out	2074 ms	1364 KB	Time limit exceeded
6	Execution timed out	2083 ms	340 KB	Time limit exceeded
7	Execution timed out	2075 ms	468 KB	Time limit exceeded
8	Incorrect	1 ms	468 KB	Output isn't correct
9	Execution timed out	2070 ms	596 KB	Time limit exceeded
10	Execution timed out	2064 ms	1236 KB	Time limit exceeded
11	Incorrect	4 ms	1108 KB	Output isn't correct
12	Execution timed out	2072 ms	1364 KB	Time limit exceeded
13	Execution timed out	2077 ms	1364 KB	Time limit exceeded
14	Execution timed out	2073 ms	1364 KB	Time limit exceeded
15	Execution timed out	2071 ms	2260 KB	Time limit exceeded
16	Execution timed out	2079 ms	2260 KB	Time limit exceeded
17	Execution timed out	2053 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	2086 ms	15444 KB	Time limit exceeded
2	Execution timed out	2065 ms	5172 KB	Time limit exceeded
3	Execution timed out	2081 ms	16176 KB	Time limit exceeded
4	Execution timed out	2032 ms	7728 KB	Time limit exceeded
5	Execution timed out	2081 ms	12132 KB	Time limit exceeded
6	Execution timed out	2045 ms	16476 KB	Time limit exceeded
7	Execution timed out	2067 ms	16212 KB	Time limit exceeded
8	Execution timed out	2082 ms	15444 KB	Time limit exceeded
9	Execution timed out	2064 ms	340 KB	Time limit exceeded
10	Execution timed out	2076 ms	340 KB	Time limit exceeded
11	Execution timed out	2048 ms	15828 KB	Time limit exceeded
12	Execution timed out	2063 ms	852 KB	Time limit exceeded
13	Execution timed out	2085 ms	5204 KB	Time limit exceeded
14	Execution timed out	2081 ms	3924 KB	Time limit exceeded
15	Execution timed out	2081 ms	4180 KB	Time limit exceeded
16	Execution timed out	2074 ms	1876 KB	Time limit exceeded
17	Execution timed out	2069 ms	8276 KB	Time limit exceeded
18	Execution timed out	2090 ms	8136 KB	Time limit exceeded
19	Execution timed out	2088 ms	7688 KB	Time limit exceeded
20	Execution timed out	2093 ms	7244 KB	Time limit exceeded
21	Execution timed out	2084 ms	12596 KB	Time limit exceeded
22	Execution timed out	2076 ms	12232 KB	Time limit exceeded
23	Execution timed out	2073 ms	10188 KB	Time limit exceeded
24	Execution timed out	2067 ms	12612 KB	Time limit exceeded
25	Execution timed out	2075 ms	16148 KB	Time limit exceeded
26	Correct	150 ms	14496 KB	Output is correct
27	Incorrect	612 ms	16596 KB	Output isn't correct
28	Execution timed out	2064 ms	16392 KB	Time limit exceeded
29	Execution timed out	2058 ms	16356 KB	Time limit exceeded
30	Execution timed out	2029 ms	16248 KB	Time limit exceeded
31	Execution timed out	2064 ms	12984 KB	Time limit exceeded
32	Execution timed out	2060 ms	16460 KB	Time limit exceeded