oj.uz

Submission #902700

# Submission time Handle Problem Language Result Execution time Memory
902700 2024-01-11T00:36:26 Z Keshav211 Tracks in the Snow (BOI13_tracks) C++14
45.3125 / 100
 2000 ms 1048576 KB 
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#define grid(n,m) for (ll i=1;i<=n;i++){for (ll j=1;j<=m;j++) cin>>graph[i][j];}
#define vll vector<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
using namespace std;
const ll inf=2*1e5+1;
const ll graph_size=4000;
// Fast Input/Output
void fastio(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
}
// File Input/Output
str fileio(const string&filePath=__FILE__){
    size_t lastSlash=filePath.find_last_of('/');
    size_t lastDot=filePath.rfind('.');
    return filePath.substr(lastSlash+1,lastDot-lastSlash-1);
}
ll n,m;
// Floodfill
ll row_num,col_num;
char graph[graph_size+2][graph_size+2];
vector<pll> directions={{0,-1},{-1,0},{1,0},{0,1}};
bool floodfill_visited[graph_size+2][graph_size+2];
vector<pll> path;
ll curr=0;
void floodfill_dfs(pll coord,char color){
    ll x=coord.first;
    ll y=coord.second;
    if (x==3 and y==4){
        ll z=1;
    }
    if ((graph[x][y]!=color and graph[x][y]!='*') or x<=0 or x>n or y<=0 or y>m or floodfill_visited[x][y]){
        return;
    }
    floodfill_visited[x][y]=1;
    if (graph[x][y]!='*'){
        curr++;
    }
    graph[x][y]='*';
    path.pb({x,y});
    for (auto i:directions){
        floodfill_dfs({x+i.first,y+i.second},color);
    }
}
int main(){
    // auto start_time=chrono::steady_clock::now();
    fastio();
    // str filename=fileio();
    // ifstream cin(filename+".in");
    // ofstream cout(filename+".out");
    ll t=1;
    // cin>>t;
    while (t--){
        cin>>n>>m;
        grid(n,m);
        ll tracks=0;
        for (ll i=1;i<=n;i++){
            for (ll j=1;j<=m;j++){
                if (graph[i][j]!='.'){
                    tracks++;
                }
            }
        }
        char animal=graph[1][1];
        ll ans=0;
        while (curr<tracks){
            ans++;
            floodfill_dfs({n,m},animal);
            for (auto i:path){
                floodfill_visited[i.first][i.second]=0;
            }
            path.clear();
            if (animal=='F'){
                animal='R';
            }
            else{
                animal='F';
            }
        }
        cout<<ans<<"\n";
    }
    // auto end_time=chrono::steady_clock::now();
    // auto elapsed_time=chrono::duration_cast<chrono::milliseconds>(end_time-start_time);
    // cout<<"Elapsed time: "<<elapsed_time.count()<<" milliseconds\n";
}

Compilation message

tracks.cpp: In function 'void floodfill_dfs(std::pair<long long int, long long int>, char)':
tracks.cpp:38:12: warning: unused variable 'z' [-Wunused-variable]
   38 |         ll z=1;
      |            ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 28360 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 31 ms 22620 KB Output is correct
5 Correct 65 ms 7136 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 2 ms 3100 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 68 ms 6904 KB Output is correct
11 Correct 8 ms 7128 KB Output is correct
12 Correct 63 ms 13276 KB Output is correct
13 Correct 69 ms 7136 KB Output is correct
14 Correct 51 ms 7132 KB Output is correct
15 Correct 444 ms 17340 KB Output is correct
16 Correct 239 ms 28512 KB Output is correct
17 Correct 393 ms 14580 KB Output is correct
18 Correct 38 ms 22504 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1862 ms 32628 KB Output is correct
2 Execution timed out 2092 ms 45480 KB Time limit exceeded
3 Execution timed out 2045 ms 49460 KB Time limit exceeded
4 Execution timed out 2051 ms 47144 KB Time limit exceeded
5 Execution timed out 2035 ms 36148 KB Time limit exceeded
6 Runtime error 1554 ms 1048576 KB Execution killed with signal 9
7 Correct 1546 ms 33252 KB Output is correct
8 Correct 1830 ms 32632 KB Output is correct
9 Correct 162 ms 5128 KB Output is correct
10 Correct 377 ms 3436 KB Output is correct
11 Correct 677 ms 32408 KB Output is correct
12 Correct 1490 ms 4336 KB Output is correct
13 Execution timed out 2016 ms 45056 KB Time limit exceeded
14 Execution timed out 2013 ms 27068 KB Time limit exceeded
15 Execution timed out 2045 ms 13564 KB Time limit exceeded
16 Execution timed out 2050 ms 24824 KB Time limit exceeded
17 Execution timed out 2027 ms 59016 KB Time limit exceeded
18 Execution timed out 2037 ms 23804 KB Time limit exceeded
19 Execution timed out 2009 ms 46724 KB Time limit exceeded
20 Execution timed out 2045 ms 21600 KB Time limit exceeded
21 Execution timed out 2031 ms 38252 KB Time limit exceeded
22 Execution timed out 2036 ms 36352 KB Time limit exceeded
23 Execution timed out 2055 ms 74620 KB Time limit exceeded
24 Execution timed out 2051 ms 37644 KB Time limit exceeded
25 Execution timed out 2033 ms 49140 KB Time limit exceeded
26 Runtime error 954 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1315 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1435 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1469 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1131 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2094 ms 313120 KB Time limit exceeded
32 Runtime error 963 ms 1048576 KB Execution killed with signal 9