oj.uz

Submission #1026814

# Submission time Handle Problem Language Result Execution time Memory
1026814 2024-07-18T11:55:04 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
47.5 / 100
 2000 ms 87236 KB 
#include <bits/stdc++.h>
using namespace std;

int h, w;
char m[4000][4000];
queue<pair<int, int> > q;
int vis[4000][4000];
vector<pair<int, int> > dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int main() {
    cin>>h>>w;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            cin>>m[i][j];
        }
    }
    int res = 1;
    char animal = m[0][0];
    bool finish = false;
    //animal = 'K';
    //cout<<"animal: "<<animal<<endl;
    while(!finish) {
        q.push({0, 0});
        finish = true;
        while(q.size()) {
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            if(vis[y][x] == res || (animal != m[y][x] && m[y][x] != 'A'))
                continue;
            if(m[y][x] != 'A')
                finish = false;
            vis[y][x] = res;
            m[y][x] = 'A';
            //cout<<res<<" "<<y<<" "<<x<<endl;
            for(auto d : dir) {
                int newY = y + d.first;
                int newX = x + d.second;
                if(newY >= 0 && newY < h && newX >= 0 && newX < w && vis[newY][newX] != res)
                    if(m[newY][newX] == animal || m[newY][newX] == 'A')
                        q.push({newY, newX});
            }
        }
        res++;
        if(animal == 'R')
            animal = 'F';
        else
            animal = 'R';
        /*
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++)
                cout<<m[i][j];
            cout<<endl;
        }
        */
    }
    cout<<res - 2<<endl;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 7504 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 25 ms 7260 KB Output is correct
5 Correct 45 ms 3836 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2756 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 59 ms 3624 KB Output is correct
11 Correct 6 ms 3420 KB Output is correct
12 Correct 58 ms 4016 KB Output is correct
13 Correct 46 ms 3828 KB Output is correct
14 Correct 44 ms 3884 KB Output is correct
15 Correct 396 ms 7252 KB Output is correct
16 Correct 174 ms 7504 KB Output is correct
17 Correct 304 ms 7504 KB Output is correct
18 Correct 25 ms 7260 KB Output is correct

Subtask #2
17.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1321 ms 32544 KB Output is correct
2 Execution timed out 2012 ms 15376 KB Time limit exceeded
3 Execution timed out 2087 ms 41356 KB Time limit exceeded
4 Execution timed out 2032 ms 29196 KB Time limit exceeded
5 Execution timed out 2013 ms 31568 KB Time limit exceeded
6 Execution timed out 2098 ms 87124 KB Time limit exceeded
7 Correct 913 ms 33112 KB Output is correct
8 Correct 1278 ms 32556 KB Output is correct
9 Correct 125 ms 2648 KB Output is correct
10 Correct 236 ms 2572 KB Output is correct
11 Correct 389 ms 32956 KB Output is correct
12 Correct 1133 ms 3156 KB Output is correct
13 Execution timed out 2053 ms 15444 KB Time limit exceeded
14 Execution timed out 2041 ms 12824 KB Time limit exceeded
15 Execution timed out 2017 ms 11604 KB Time limit exceeded
16 Execution timed out 2064 ms 8020 KB Time limit exceeded
17 Execution timed out 2058 ms 25140 KB Time limit exceeded
18 Execution timed out 2021 ms 21072 KB Time limit exceeded
19 Execution timed out 2057 ms 29268 KB Time limit exceeded
20 Execution timed out 2044 ms 17900 KB Time limit exceeded
21 Execution timed out 2027 ms 32600 KB Time limit exceeded
22 Execution timed out 2104 ms 31780 KB Time limit exceeded
23 Execution timed out 2087 ms 31964 KB Time limit exceeded
24 Execution timed out 2040 ms 32264 KB Time limit exceeded
25 Execution timed out 2058 ms 41072 KB Time limit exceeded
26 Correct 883 ms 78080 KB Output is correct
27 Execution timed out 2019 ms 87124 KB Time limit exceeded
28 Execution timed out 2096 ms 87236 KB Time limit exceeded
29 Execution timed out 2083 ms 87076 KB Time limit exceeded
30 Execution timed out 2065 ms 86352 KB Time limit exceeded
31 Execution timed out 2080 ms 47884 KB Time limit exceeded
32 Execution timed out 2094 ms 86472 KB Time limit exceeded