oj.uz

Submission #639539

# Submission time Handle Problem Language Result Execution time Memory
639539 2022-09-10T14:20:47 Z AdiCoder03 Tracks in the Snow (BOI13_tracks) C++17
80.3125 / 100
 2000 ms 1048576 KB 
#include<bits/stdc++.h>
typedef long long ll;

#define vi vector<int>
#define pb push_back
#define self_min(a, b) a = min(a, b)
#define self_max(a, b) a = max(a, b)
#define V vector
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define fs(lcv, hi) for(lcv = 0; lcv < hi; lcv ++)
#define fb(lcv, hi) for(lcv = hi; lcv >= 0; lcv --)
#define loop(lcv, lower, upper) for(lcv = lower; lcv < upper; lcv++)
#define crd(pii) [pii.first][pii.second]

using namespace std;

V<vi> grid;
V<V<V<pair<int, pair<int, int>>>>> adj;
V<V<bool>> vis;
V<V<int>> distances;
int h, w;

void flood_fill(int x, int y);

void process(int x1, int y1, int x2, int y2)
{
    if(x1 < 0 || x1 > h - 1 || y1 < 0 || y1 > w-1 || !grid[x1][y1]) return;
    if(grid[x1][y1] == grid[x2][y2])
    {
        adj[x1][y1].pb({0, {x2, y2}});
        adj[x2][y2].pb({0, {x1, y1}});
    }
    else
    {
        adj[x1][y1].pb({1, {x2, y2}});
        adj[x2][y2].pb({1, {x1, y1}});
    }
    if(!vis[x1][y1])
    flood_fill(x1, y1);
}

void flood_fill(int x, int y)
{
    vis[x][y] = 1;
    process(x - 1, y, x, y);
    process(x, y - 1, x, y);
    process(x + 1, y, x, y);
    process(x, y + 1, x, y);
}

int find_max(int x, int y)
{
    deque<pair<int, int>> bfsq;
    bfsq.push_back({x, y});
    distances[x][y] = 0;
    int res = 0;
    while(!bfsq.empty())
    {
        pair<int, int> tp = bfsq.front();
        bfsq.pop_front();
        // vis[tp.first][tp.second] = 1;
        for(auto x : adj crd(tp))
        {
            if(distances crd(x.second) > distances crd(tp) + x.first)
            {
                distances crd(x.second) = distances crd(tp) + x.first;
                if(x.first) bfsq.push_back(x.second);
                else bfsq.push_front(x.second);
                self_max(res, distances crd(x.second));
                // vis crd(x.second) = 1;
            }
        }
    }
    return res;
}

void solve()
{
    int i, j;
    cin >> h >> w;
    grid.assign(h, vi(w, 0));
    vis.assign(h, V<bool> (w, 0));
    adj.assign(h, V<V<pair<int, pair<int, int>>>>(w));
    fs(i, h)
    {
        string row;
        cin >> row;
        fs(j, w)
        {
            if(row[j] == 'F') grid[i][j] = 1;
            else if(row[j] == 'R') grid[i][j] = 2;
        }
    }
    flood_fill(0, 0);
    distances.assign(h, vi(w, (int)1e9));
    cout << 1 + find_max(0, 0) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 46808 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 72 ms 31848 KB Output is correct
5 Correct 8 ms 4948 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 1236 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 12 ms 5452 KB Output is correct
11 Correct 18 ms 8544 KB Output is correct
12 Correct 38 ms 16348 KB Output is correct
13 Correct 9 ms 5024 KB Output is correct
14 Correct 8 ms 4948 KB Output is correct
15 Correct 81 ms 32180 KB Output is correct
16 Correct 115 ms 46796 KB Output is correct
17 Correct 52 ms 20552 KB Output is correct
18 Correct 76 ms 31956 KB Output is correct

Subtask #2
50.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3812 KB Output is correct
2 Correct 270 ms 125708 KB Output is correct
3 Correct 1483 ms 898380 KB Output is correct
4 Correct 358 ms 173808 KB Output is correct
5 Correct 1067 ms 644800 KB Output is correct
6 Runtime error 1539 ms 1048576 KB Execution killed with signal 9
7 Correct 5 ms 3412 KB Output is correct
8 Correct 6 ms 3816 KB Output is correct
9 Correct 11 ms 5964 KB Output is correct
10 Correct 3 ms 1876 KB Output is correct
11 Correct 4 ms 3156 KB Output is correct
12 Correct 3 ms 2132 KB Output is correct
13 Correct 279 ms 125680 KB Output is correct
14 Correct 166 ms 73092 KB Output is correct
15 Correct 146 ms 59804 KB Output is correct
16 Correct 153 ms 64712 KB Output is correct
17 Correct 747 ms 317628 KB Output is correct
18 Correct 546 ms 234060 KB Output is correct
19 Correct 339 ms 173648 KB Output is correct
20 Correct 330 ms 201468 KB Output is correct
21 Correct 829 ms 528500 KB Output is correct
22 Correct 1075 ms 644700 KB Output is correct
23 Correct 1357 ms 620532 KB Output is correct
24 Correct 820 ms 530480 KB Output is correct
25 Execution timed out 2059 ms 947900 KB Time limit exceeded
26 Runtime error 1690 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1501 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1513 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1486 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1480 ms 1048576 KB Execution killed with signal 9
31 Runtime error 1779 ms 1048576 KB Execution killed with signal 9
32 Runtime error 1464 ms 1048576 KB Execution killed with signal 9