oj.uz

Submission #902693

# Submission time Handle Problem Language Result Execution time Memory
902693 2024-01-11T00:24:23 Z Keshav211 Tracks in the Snow (BOI13_tracks) C++14
32.1875 / 100
 2000 ms 26648 KB 
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <chrono>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <climits>
#include <bitset>
#define all(x) (x).begin(), (x).end()
#define vec(n) vll arr(n);
#define printarr(arr) for(auto i:arr)cout<<i<<" "; cout<<endl;
#define printdict(dict) for(auto i:dict)cout<<i.first<<": "<<i.second<<endl;
#define printadj(adj) for(ll i=0;i<n;i++){if(!adj[i].empty()){cout<<i<<": ";printarr(adj[i])}}
#define read(arr); for(ll i=0;i<arr.size();i++) cin>>arr[i];
#define readundirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].push_back(b);adj[b].push_back(a);}
#define readdirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].push_back(b);}
#define readfunc(n) for(ll i=0;i<n;i++){ll a;cin>>a;a--;func_adj[i]=a;}
#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 sll set<ll>
#define msll multiset<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
#define ld long double
using namespace std;
const str alph="abcdefghijklmnopqrstuvwxyz";
const str capalph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll inf=2*1e5+1;
const ll graph_size=1000;
const ll mod=1e9+7;
const ll large=1e18;
const ll small=-1e18;
// 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);
}
// For Yes Or No Problems
str yes_or_no(bool test){
    if (test){
       return "YES";
    }
    return "NO";
}
ll n,m,q;
// 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);
    }
}
ll floodfill_level[graph_size+2][graph_size+2];
void floodfill_bfs(pll coord,char color){
    ll x=coord.first;
    ll y=coord.second;
    queue<pair<ll,ll>> Q;
    Q.push({x,y});
    floodfill_level[x][y]=0;
    while (!Q.empty()){
        pll curr=Q.front();
        Q.pop();
        x=curr.first;
        y=curr.second;
        floodfill_visited[x][y]=1;
        for (auto i:directions){
            if (graph[x+i.first][y+i.second]==color and  x+i.first>=1 and x+i.first<=n and y+i.second>=1 and y+i.second<=n){
                floodfill_level[x+i.first][y+i.second]=floodfill_level[x][y]+1;
                Q.push({x+i.first,y+i.second});
            }
        }
    }
}
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:74:12: warning: unused variable 'z' [-Wunused-variable]
   74 |         ll z=1;
      |            ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 26400 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 3 ms 4580 KB Output is correct
4 Correct 47 ms 21064 KB Output is correct
5 Correct 70 ms 6064 KB Output is correct
6 Correct 1 ms 4456 KB Output is correct
7 Correct 3 ms 4456 KB Output is correct
8 Correct 2 ms 5100 KB Output is correct
9 Correct 3 ms 4712 KB Output is correct
10 Correct 106 ms 6016 KB Output is correct
11 Correct 7 ms 8420 KB Output is correct
12 Correct 110 ms 12124 KB Output is correct
13 Correct 75 ms 6076 KB Output is correct
14 Correct 72 ms 6052 KB Output is correct
15 Correct 816 ms 16760 KB Output is correct
16 Correct 416 ms 26648 KB Output is correct
17 Correct 592 ms 12712 KB Output is correct
18 Correct 46 ms 19664 KB Output is correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 9560 KB Execution killed with signal 11
2 Runtime error 15 ms 10824 KB Execution killed with signal 11
3 Runtime error 58 ms 13512 KB Execution killed with signal 11
4 Runtime error 23 ms 11604 KB Execution killed with signal 11
5 Runtime error 29 ms 12636 KB Execution killed with signal 11
6 Runtime error 52 ms 13516 KB Execution killed with signal 11
7 Runtime error 5 ms 9560 KB Execution killed with signal 11
8 Runtime error 7 ms 9564 KB Execution killed with signal 11
9 Execution timed out 2090 ms 4580 KB Time limit exceeded
10 Execution timed out 2031 ms 4440 KB Time limit exceeded
11 Runtime error 5 ms 9564 KB Execution killed with signal 11
12 Correct 1532 ms 6088 KB Output is correct
13 Runtime error 15 ms 10836 KB Execution killed with signal 11
14 Execution timed out 2062 ms 22076 KB Time limit exceeded
15 Execution timed out 2044 ms 7488 KB Time limit exceeded
16 Execution timed out 2057 ms 6176 KB Time limit exceeded
17 Runtime error 24 ms 11600 KB Execution killed with signal 11
18 Runtime error 27 ms 11608 KB Execution killed with signal 11
19 Runtime error 21 ms 11620 KB Execution killed with signal 11
20 Runtime error 30 ms 11612 KB Execution killed with signal 11
21 Runtime error 30 ms 12628 KB Execution killed with signal 11
22 Runtime error 32 ms 12856 KB Execution killed with signal 11
23 Runtime error 35 ms 12684 KB Execution killed with signal 11
24 Runtime error 34 ms 12512 KB Execution killed with signal 11
25 Runtime error 45 ms 13644 KB Execution killed with signal 11
26 Runtime error 41 ms 13060 KB Execution killed with signal 11
27 Runtime error 40 ms 13508 KB Execution killed with signal 11
28 Runtime error 38 ms 13624 KB Execution killed with signal 11
29 Runtime error 38 ms 13652 KB Execution killed with signal 11
30 Runtime error 50 ms 13652 KB Execution killed with signal 11
31 Runtime error 31 ms 12884 KB Execution killed with signal 11
32 Runtime error 40 ms 13504 KB Execution killed with signal 11