oj.uz

Submission #1039179

# Submission time Handle Problem Language Result Execution time Memory
1039179 2024-07-30T14:10:24 Z biserailieva Tracks in the Snow (BOI13_tracks) C++14
47.5 / 100
 2000 ms 94452 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;
    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';
            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';
    }
    cout<<res - 2<<endl;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 5460 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 21 ms 4972 KB Output is correct
5 Correct 43 ms 2904 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 51 ms 2396 KB Output is correct
11 Correct 7 ms 2136 KB Output is correct
12 Correct 48 ms 3184 KB Output is correct
13 Correct 43 ms 2908 KB Output is correct
14 Correct 41 ms 2908 KB Output is correct
15 Correct 310 ms 5204 KB Output is correct
16 Correct 137 ms 5460 KB Output is correct
17 Correct 251 ms 5200 KB Output is correct
18 Correct 21 ms 4952 KB Output is correct

Subtask #2
17.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1276 ms 30996 KB Output is correct
2 Execution timed out 2033 ms 14672 KB Time limit exceeded
3 Execution timed out 2041 ms 47996 KB Time limit exceeded
4 Execution timed out 2058 ms 28084 KB Time limit exceeded
5 Execution timed out 2045 ms 33104 KB Time limit exceeded
6 Execution timed out 2025 ms 94360 KB Time limit exceeded
7 Correct 949 ms 32600 KB Output is correct
8 Correct 1260 ms 31056 KB Output is correct
9 Correct 99 ms 768 KB Output is correct
10 Correct 185 ms 564 KB Output is correct
11 Correct 364 ms 31648 KB Output is correct
12 Correct 1048 ms 1628 KB Output is correct
13 Execution timed out 2056 ms 14676 KB Time limit exceeded
14 Execution timed out 2073 ms 10456 KB Time limit exceeded
15 Execution timed out 2060 ms 9464 KB Time limit exceeded
16 Execution timed out 2045 ms 5716 KB Time limit exceeded
17 Execution timed out 2059 ms 24760 KB Time limit exceeded
18 Execution timed out 2069 ms 20304 KB Time limit exceeded
19 Execution timed out 2041 ms 28296 KB Time limit exceeded
20 Execution timed out 2009 ms 18012 KB Time limit exceeded
21 Execution timed out 2067 ms 34444 KB Time limit exceeded
22 Execution timed out 2060 ms 33072 KB Time limit exceeded
23 Execution timed out 2066 ms 32796 KB Time limit exceeded
24 Execution timed out 2055 ms 34152 KB Time limit exceeded
25 Execution timed out 2041 ms 47800 KB Time limit exceeded
26 Correct 847 ms 80724 KB Output is correct
27 Execution timed out 2051 ms 94452 KB Time limit exceeded
28 Execution timed out 2047 ms 94292 KB Time limit exceeded
29 Execution timed out 2075 ms 94288 KB Time limit exceeded
30 Execution timed out 2044 ms 92504 KB Time limit exceeded
31 Execution timed out 2037 ms 52336 KB Time limit exceeded
32 Execution timed out 2105 ms 93520 KB Time limit exceeded