oj.uz

Submission #812244

# Submission time Handle Problem Language Result Execution time Memory
812244 2023-08-07T07:58:22 Z makanhulia Tracks in the Snow (BOI13_tracks) C++17
30 / 100
 2000 ms 9048 KB 
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define REP(i,a,b)for(int i=a;i<b;i++)
#define fi first
#define se second
using namespace std;
using pii=pair<int, int>;

int color[1000][1000];
bool visited[1000][1000];
int on=0;
int col=-1;
int h, w;

void bfs() {
    queue<pii> q;
    q.push({0,0});
    while(q.size()){
        auto top=q.front();
        q.pop();
        if(top.fi<0)continue;
        if(top.fi>=h)continue;
        if(top.se<0)continue;
        if(top.se>=w)continue;
        if(visited[top.fi][top.se])continue;
        visited[top.fi][top.se]=true;
        if((color[top.fi][top.se]!=col) && (color[top.fi][top.se]!=(-1))){
            continue;
        }
        if(color[top.fi][top.se]!=(-1))on--;
        color[top.fi][top.se]=-1;
        q.push({top.fi+1, top.se});
        q.push({top.fi-1, top.se});
        q.push({top.fi, top.se+1});
        q.push({top.fi, top.se-1});
    }
}

#undef int
int main() {
#define int long long
    cin>>h>>w;
    assert(max(h, w)<1000);
    REP(i,0,h){
        REP(j,0,w){
            char c;cin>>c;
            if(c=='.')color[i][j]=0;
            if(c=='R')color[i][j]=1;
            if(c=='F')color[i][j]=2;
            if(color[i][j])on++;
        }
    }
    col=color[0][0];
    int ans=0;
    // on=1;
    while(true){
        ans++;
        bfs();
        memset(visited,0,sizeof visited);
        bool clear=true;
        REP(i,0,h){
            REP(j,0,w){
                if(color[i][j]>=1)clear=false;
                // cout<<color[i][j]<<" ";
                // if(color[i][j]!=-1)cout<<" ";
            }
            // cout<<endl;
        }
        if(clear)break;
        col = 3-col;
    }
    cout<<ans<<endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 5120 KB Output is correct
2 Correct 4 ms 1236 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 36 ms 4436 KB Output is correct
5 Correct 89 ms 3072 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 3 ms 1492 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 5 ms 1748 KB Output is correct
10 Correct 122 ms 2644 KB Output is correct
11 Correct 8 ms 2396 KB Output is correct
12 Correct 93 ms 3112 KB Output is correct
13 Correct 87 ms 3068 KB Output is correct
14 Correct 91 ms 3056 KB Output is correct
15 Correct 759 ms 5196 KB Output is correct
16 Correct 303 ms 5120 KB Output is correct
17 Correct 534 ms 4948 KB Output is correct
18 Correct 33 ms 4436 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Runtime error 1 ms 340 KB Execution killed with signal 6
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Runtime error 1 ms 448 KB Execution killed with signal 6
7 Runtime error 1 ms 468 KB Execution killed with signal 6
8 Runtime error 1 ms 340 KB Execution killed with signal 6
9 Runtime error 1 ms 340 KB Execution killed with signal 6
10 Runtime error 1 ms 468 KB Execution killed with signal 6
11 Runtime error 1 ms 468 KB Execution killed with signal 6
12 Execution timed out 2073 ms 2004 KB Time limit exceeded
13 Runtime error 1 ms 468 KB Execution killed with signal 6
14 Execution timed out 2069 ms 8524 KB Time limit exceeded
15 Execution timed out 2079 ms 9048 KB Time limit exceeded
16 Runtime error 1 ms 468 KB Execution killed with signal 6
17 Runtime error 1 ms 468 KB Execution killed with signal 6
18 Runtime error 1 ms 468 KB Execution killed with signal 6
19 Runtime error 1 ms 468 KB Execution killed with signal 6
20 Runtime error 1 ms 340 KB Execution killed with signal 6
21 Runtime error 1 ms 468 KB Execution killed with signal 6
22 Runtime error 1 ms 340 KB Execution killed with signal 6
23 Runtime error 1 ms 340 KB Execution killed with signal 6
24 Runtime error 1 ms 468 KB Execution killed with signal 6
25 Runtime error 1 ms 468 KB Execution killed with signal 6
26 Runtime error 1 ms 468 KB Execution killed with signal 6
27 Runtime error 1 ms 340 KB Execution killed with signal 6
28 Runtime error 1 ms 468 KB Execution killed with signal 6
29 Runtime error 1 ms 468 KB Execution killed with signal 6
30 Runtime error 1 ms 468 KB Execution killed with signal 6
31 Runtime error 1 ms 340 KB Execution killed with signal 6
32 Runtime error 1 ms 448 KB Execution killed with signal 6