oj.uz

Submission #877556

# Submission time Handle Problem Language Result Execution time Memory
877556 2023-11-23T10:17:10 Z asli_bg Tracks in the Snow (BOI13_tracks) C++11
47.5 / 100
 2000 ms 141396 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define MOD 1000000007

const int MAXN=4e3+1;

int vis[MAXN][MAXN];

int grid[MAXN][MAXN];

int h,w;

int xyon[5]={1,0,-1,0};
int yyon[5]={0,-1,0,1};

int say=0;

bool isvalid(int x,int y,int deg){
    if(x>=h or x<0 or y>=w or y<0) return false;
    if(grid[x][y]==-1) return false;
    if(grid[x][y]!=deg) return false;
    return true;
}

void bfs(int x,int y){
    queue<pii> q;
    q.push({x,y});
    vis[x][y]=true;
    say++;

    int deg=grid[x][y];

    grid[x][y]=!deg;

    while(!q.empty()){
        auto el=q.front();
        q.pop();

        for(int i=0;i<4;i++){
            int newx=el.fi+xyon[i];
            int newy=el.se+yyon[i];

            if(isvalid(newx,newy,deg) and !vis[newx][newy]){
                //cout<<grid[el.fi][el.se]<<"-->"<<grid[newx][newy]<<endl;
                vis[newx][newy]=true;
                q.push({newx,newy});
                grid[newx][newy]=!deg;
                say++;

            }

        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
 
    //ifstream cin("lepus.in");
    //ofstream cout("lepus.out");

    cin>>h>>w;

    map<char,int> anim;
    anim['F']=1;
    anim['R']=0;
    anim['.']=-1;

    int all_steps=0;

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            char c;
            cin>>c;
            grid[i][j]=anim[c];
            if(grid[i][j]!=-1){
                all_steps++;
            }
        }
    }

    //cout<<all_steps<<endl;

    

    int cev=0;

    while(all_steps!=say){
        say=0;
        bfs(0,0);
        //cout<<"s: "<<say<<endl;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                vis[i][j]=false;
            }
        }
        cev++;
    }

    cout<<cev<<endl;

    /*for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout<<grid[i][j]<<' ';
        }
        cout<<endl;
    }*/

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 13400 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4556 KB Output is correct
4 Correct 14 ms 12892 KB Output is correct
5 Correct 45 ms 9792 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 49 ms 7612 KB Output is correct
11 Correct 4 ms 7260 KB Output is correct
12 Correct 35 ms 9820 KB Output is correct
13 Correct 45 ms 9820 KB Output is correct
14 Correct 44 ms 9820 KB Output is correct
15 Correct 276 ms 13568 KB Output is correct
16 Correct 107 ms 13400 KB Output is correct
17 Correct 276 ms 13404 KB Output is correct
18 Correct 13 ms 12892 KB Output is correct

Subtask #2
17.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1823 ms 79452 KB Output is correct
2 Execution timed out 2051 ms 34908 KB Time limit exceeded
3 Execution timed out 2025 ms 141340 KB Time limit exceeded
4 Execution timed out 2087 ms 58436 KB Time limit exceeded
5 Execution timed out 2040 ms 104276 KB Time limit exceeded
6 Execution timed out 2033 ms 141392 KB Time limit exceeded
7 Correct 1325 ms 79964 KB Output is correct
8 Correct 1789 ms 79428 KB Output is correct
9 Correct 83 ms 4700 KB Output is correct
10 Correct 221 ms 2648 KB Output is correct
11 Correct 525 ms 79828 KB Output is correct
12 Correct 1075 ms 7024 KB Output is correct
13 Execution timed out 2054 ms 35024 KB Time limit exceeded
14 Execution timed out 2056 ms 24412 KB Time limit exceeded
15 Execution timed out 2048 ms 27228 KB Time limit exceeded
16 Execution timed out 2056 ms 12600 KB Time limit exceeded
17 Execution timed out 2057 ms 62296 KB Time limit exceeded
18 Execution timed out 2058 ms 62156 KB Time limit exceeded
19 Execution timed out 2035 ms 58552 KB Time limit exceeded
20 Execution timed out 2017 ms 54328 KB Time limit exceeded
21 Execution timed out 2015 ms 108368 KB Time limit exceeded
22 Execution timed out 2037 ms 104416 KB Time limit exceeded
23 Execution timed out 2099 ms 87408 KB Time limit exceeded
24 Execution timed out 2051 ms 107624 KB Time limit exceeded
25 Execution timed out 2016 ms 141136 KB Time limit exceeded
26 Correct 477 ms 123728 KB Output is correct
27 Execution timed out 2052 ms 141328 KB Time limit exceeded
28 Execution timed out 2015 ms 141136 KB Time limit exceeded
29 Execution timed out 2044 ms 141396 KB Time limit exceeded
30 Execution timed out 2008 ms 139600 KB Time limit exceeded
31 Execution timed out 2045 ms 112976 KB Time limit exceeded
32 Execution timed out 2032 ms 141392 KB Time limit exceeded