oj.uz

Submission #902698

# Submission time Handle Problem Language Result Execution time Memory
902698 2024-01-11T00:30:56 Z Keshav211 Tracks in the Snow (BOI13_tracks) C++14
40.9375 / 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];
bool seen[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 !seen[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 (!seen[x][y]){
        curr++;
    }
    seen[x][y]=1;
    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:39:12: warning: unused variable 'z' [-Wunused-variable]
   39 |         ll z=1;
      |            ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 30332 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 3 ms 2776 KB Output is correct
4 Correct 33 ms 24564 KB Output is correct
5 Correct 74 ms 6260 KB Output is correct
6 Correct 1 ms 2512 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 3 ms 3420 KB Output is correct
10 Correct 109 ms 5684 KB Output is correct
11 Correct 12 ms 8024 KB Output is correct
12 Correct 109 ms 12244 KB Output is correct
13 Correct 73 ms 6276 KB Output is correct
14 Correct 71 ms 6288 KB Output is correct
15 Correct 813 ms 20472 KB Output is correct
16 Correct 422 ms 30708 KB Output is correct
17 Correct 581 ms 16460 KB Output is correct
18 Correct 46 ms 24928 KB Output is correct

Subtask #2
10.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 47156 KB Time limit exceeded
2 Execution timed out 2070 ms 38804 KB Time limit exceeded
3 Execution timed out 2043 ms 65144 KB Time limit exceeded
4 Execution timed out 2040 ms 49396 KB Time limit exceeded
5 Execution timed out 2017 ms 46084 KB Time limit exceeded
6 Runtime error 1650 ms 1048576 KB Execution killed with signal 9
7 Correct 1998 ms 49056 KB Output is correct
8 Execution timed out 2037 ms 47208 KB Time limit exceeded
9 Correct 252 ms 5216 KB Output is correct
10 Correct 428 ms 3476 KB Output is correct
11 Correct 752 ms 47852 KB Output is correct
12 Correct 1503 ms 4924 KB Output is correct
13 Execution timed out 2073 ms 39140 KB Time limit exceeded
14 Execution timed out 2035 ms 29520 KB Time limit exceeded
15 Execution timed out 2020 ms 16988 KB Time limit exceeded
16 Execution timed out 2007 ms 25708 KB Time limit exceeded
17 Execution timed out 2025 ms 65300 KB Time limit exceeded
18 Execution timed out 2031 ms 32064 KB Time limit exceeded
19 Execution timed out 2007 ms 49580 KB Time limit exceeded
20 Execution timed out 2069 ms 27852 KB Time limit exceeded
21 Execution timed out 2041 ms 50724 KB Time limit exceeded
22 Execution timed out 2037 ms 46320 KB Time limit exceeded
23 Execution timed out 2044 ms 73976 KB Time limit exceeded
24 Execution timed out 2056 ms 49540 KB Time limit exceeded
25 Execution timed out 2051 ms 64624 KB Time limit exceeded
26 Runtime error 1010 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1388 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1561 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1472 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1130 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2028 ms 277264 KB Time limit exceeded
32 Runtime error 930 ms 1048576 KB Execution killed with signal 9