oj.uz

Submission #1108167

# Submission time Handle Problem Language Result Execution time Memory
1108167 2024-11-03T06:41:09 Z polarity Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1571 ms 864136 KB 
/**
 * Solution by 1egend (polarity.sh)
 * Date: 2024-10-30
 * Contest: BOI 2013
 * Problem: tracks
**/

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ull unsigned long long
#define ll long long

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;

vector<pair<int, int>> cardinal = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<vector<int>> grid;
vector<vector<int>> component;

void floodfill(int i, int j, int n, int l){
    if (grid[i][j] != l || component[i][j] != 0){
        return;
    }

    component[i][j] = n;

    for (pair<int, int> t : cardinal){
        floodfill(i + t.first, j + t.second, n, l);
    }
}

void solve(){
    int h, w; cin >> h >> w;
    grid = vector<vector<int>>(h + 2, vector<int>(w + 2, 0));
    component = grid;
    for (int i = 0; i < h; i++){
        string s; cin >> s;
        for (int j = 0; j < w; j++){
            char t = s[j];

            if (t == 'F'){
                grid[i + 1][j + 1] = 2;
            } else if (t == 'R'){
                grid[i + 1][j + 1] = 1;
            }
        }
    }

    int k = 1;

    for (int i = 1; i < h + 1; i++){
        for (int j = 1; j < w + 1; j++){
            if (component[i][j] == 0 && grid[i][j] != 0){
                floodfill(i, j, k, grid[i][j]);
                k++;
            }
        }
    }

    vector<vector<int>> adj(k + 1);

    for (int i = 1; i < h + 1; i++){
        for (int j = 1; j < w + 1; j++){
            int x = component[i][j];
            for (pair<int, int> t : cardinal){
                int y = component[i + t.first][j + t.second];
                if (x != 0 && y != 0 && x != y){
                    adj[x].pb(y);
                    adj[y].pb(x);
                }
            }
        }
    }

    vector<int> dist(k + 1, -1);

    int ans = 0;

    queue<int> curr;
    curr.push(1);
    dist[1] = 0;

    while(!curr.empty()){
        int comp = curr.front();
        curr.pop();
        
        for (int node : adj[comp]){
            if (dist[node] != -1){
                continue;
            }

            dist[node] = dist[comp] + 1;
            ans = max(ans, dist[node]);

            curr.push(node);
        }
    }

    cout << ans + 1 << endl;
}

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8824 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 11 ms 3276 KB Output is correct
5 Correct 5 ms 1616 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 5 ms 1804 KB Output is correct
11 Correct 3 ms 1360 KB Output is correct
12 Correct 13 ms 3576 KB Output is correct
13 Correct 5 ms 1616 KB Output is correct
14 Correct 5 ms 1616 KB Output is correct
15 Correct 27 ms 7248 KB Output is correct
16 Correct 33 ms 8788 KB Output is correct
17 Correct 20 ms 5468 KB Output is correct
18 Correct 10 ms 3276 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1616 KB Output is correct
2 Correct 110 ms 32508 KB Output is correct
3 Correct 736 ms 242640 KB Output is correct
4 Correct 144 ms 47196 KB Output is correct
5 Correct 697 ms 338196 KB Output is correct
6 Correct 982 ms 273468 KB Output is correct
7 Correct 3 ms 1616 KB Output is correct
8 Correct 4 ms 1748 KB Output is correct
9 Correct 4 ms 1872 KB Output is correct
10 Correct 2 ms 1104 KB Output is correct
11 Correct 3 ms 1360 KB Output is correct
12 Correct 2 ms 1204 KB Output is correct
13 Correct 114 ms 31972 KB Output is correct
14 Correct 58 ms 18508 KB Output is correct
15 Correct 54 ms 16716 KB Output is correct
16 Correct 54 ms 15944 KB Output is correct
17 Correct 266 ms 80200 KB Output is correct
18 Correct 241 ms 65196 KB Output is correct
19 Correct 170 ms 49492 KB Output is correct
20 Correct 155 ms 55236 KB Output is correct
21 Correct 390 ms 139848 KB Output is correct
22 Correct 675 ms 338924 KB Output is correct
23 Correct 531 ms 153992 KB Output is correct
24 Correct 406 ms 164424 KB Output is correct
25 Correct 1158 ms 260332 KB Output is correct
26 Correct 1134 ms 864136 KB Output is correct
27 Correct 741 ms 314924 KB Output is correct
28 Correct 978 ms 271216 KB Output is correct
29 Correct 909 ms 252352 KB Output is correct
30 Correct 815 ms 277132 KB Output is correct
31 Correct 1571 ms 353448 KB Output is correct
32 Correct 849 ms 411692 KB Output is correct