oj.uz

Submission #800558

# Submission time Handle Problem Language Result Execution time Memory
800558 2023-08-01T16:09:27 Z synthesis Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1874 ms 716952 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
using ull = unsigned long long int;

constexpr ll mod = 1e9 + 7;
constexpr ll INF = LONG_LONG_MAX;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int main()
{
    //tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> q;
    /*freopen("problemname.in", "r", stdin);
    freopen("problemname.out", "w", stdout);*/
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    char a[n][m];
    for(int i = 0;i<n;++i) {
        for(int j = 0;j<m;++j) {
            cin >> a[i][j];
        }
    }
    int c = -1;
    int cmp[n][m];
    memset(cmp, -1, sizeof cmp);
    bool vis[n][m];
    memset(vis, false, sizeof vis);
    for(int i = 0;i<n;++i) {
        for(int j = 0;j<m;++j) {
            if (!vis[i][j] && (a[i][j] == 'F' || a[i][j] == 'R')) {
                queue<pii> q;
                q.push({i, j});
                vis[i][j] = true;
                cmp[i][j] = ++c;
                while(!q.empty()) {
                    pii node = q.front();
                    q.pop();
                    for(int k = 0;k<4;++k) {
                        int x = node.fi + dx[k], y = node.se + dy[k];
                        if (x >= 0 && y >= 0 && x < n && y < m) {
                            if (!vis[x][y] && a[x][y] == a[i][j]) {
                                vis[x][y] = true;
                                cmp[x][y] = c;
                                q.push({x, y});
                            }
                        }
                    }
                }
            }
        }
    }
    set<int> adj[c + 1];
    memset(vis, false, sizeof vis);
    for(int i = 0;i<n;++i) {
        for(int j = 0;j<m;++j) {
            if (!vis[i][j] && (a[i][j] == 'F' || a[i][j] == 'R')) {
                queue<pii> q;
                q.push({i, j});
                vis[i][j] = true;
                while(!q.empty()) {
                    pii node = q.front();
                    q.pop();
                    for(int k = 0;k<4;++k) {
                        int x = node.fi + dx[k], y = node.se + dy[k];
                        if (x >= 0 && y >= 0 && x < n && y < m) {
                            if (!vis[x][y] && a[x][y] == a[i][j]) {
                                vis[x][y] = true;
                                q.push({x, y});
                            }
                            if (a[x][y] != a[i][j] && a[x][y] != '.') {
                                adj[cmp[i][j]].insert(cmp[x][y]);
                            }
                        }
                    }
                }
            }
        }
    }
    int d[c + 1];
    d[0] = 0;
    queue<int> q;
    q.push(0);
    bool vv[c + 1];
    memset(vv, false, sizeof vv);
    vv[0] = true;
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        for(const int& v:adj[node]) {
            if (!vv[v]) {
                vv[v] = true;
                d[v] = d[node] + 1;
                q.push(v);
            }
        }
    }
    cout << *max_element(d, d + c + 1) + 1 << endl;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8872 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 13 ms 1748 KB Output is correct
5 Correct 6 ms 2124 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 5 ms 2004 KB Output is correct
11 Correct 3 ms 684 KB Output is correct
12 Correct 16 ms 3376 KB Output is correct
13 Correct 5 ms 2120 KB Output is correct
14 Correct 5 ms 2140 KB Output is correct
15 Correct 33 ms 8448 KB Output is correct
16 Correct 48 ms 8768 KB Output is correct
17 Correct 26 ms 8012 KB Output is correct
18 Correct 13 ms 1748 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB Output is correct
2 Correct 143 ms 43120 KB Output is correct
3 Correct 859 ms 333576 KB Output is correct
4 Correct 183 ms 65228 KB Output is correct
5 Correct 1171 ms 716840 KB Output is correct
6 Correct 1772 ms 191784 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 3 ms 1364 KB Output is correct
9 Correct 5 ms 1744 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 2 ms 840 KB Output is correct
12 Correct 3 ms 2004 KB Output is correct
13 Correct 141 ms 43088 KB Output is correct
14 Correct 77 ms 25176 KB Output is correct
15 Correct 75 ms 27892 KB Output is correct
16 Correct 70 ms 19808 KB Output is correct
17 Correct 372 ms 111408 KB Output is correct
18 Correct 324 ms 108016 KB Output is correct
19 Correct 178 ms 65280 KB Output is correct
20 Correct 211 ms 74828 KB Output is correct
21 Correct 481 ms 197776 KB Output is correct
22 Correct 1141 ms 716952 KB Output is correct
23 Correct 648 ms 214448 KB Output is correct
24 Correct 587 ms 280696 KB Output is correct
25 Correct 1492 ms 441932 KB Output is correct
26 Correct 881 ms 84220 KB Output is correct
27 Correct 1100 ms 112448 KB Output is correct
28 Correct 1735 ms 191828 KB Output is correct
29 Correct 1624 ms 158292 KB Output is correct
30 Correct 1371 ms 141832 KB Output is correct
31 Correct 1874 ms 357264 KB Output is correct
32 Correct 951 ms 129908 KB Output is correct