oj.uz

Submission #1106730

# Submission time Handle Problem Language Result Execution time Memory
1106730 2024-10-31T01:54:52 Z polarity Tracks in the Snow (BOI13_tracks) C++17
40.8333 / 100
 1174 ms 1048576 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);

    vector<vector<int>> edge(k + 2, vector<int>(k + 2, 0));

    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 && edge[x][y] == 0 && edge[y][x] == 0){
                    edge[x][y] = 1;
                    edge[y][x] = 1;
                    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
23.3333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 638 ms 1048576 KB Execution killed with signal 9
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 30 ms 39296 KB Output is correct
5 Correct 146 ms 231240 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 2 ms 1872 KB Output is correct
10 Correct 153 ms 246368 KB Output is correct
11 Correct 5 ms 4432 KB Output is correct
12 Correct 379 ms 598088 KB Output is correct
13 Correct 144 ms 231240 KB Output is correct
14 Correct 145 ms 231328 KB Output is correct
15 Runtime error 649 ms 1048576 KB Execution killed with signal 9
16 Runtime error 685 ms 1048576 KB Execution killed with signal 9
17 Runtime error 694 ms 1048576 KB Execution killed with signal 9
18 Correct 31 ms 39240 KB Output is correct

Subtask #2
17.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 103784 KB Output is correct
2 Runtime error 714 ms 1048576 KB Execution killed with signal 9
3 Runtime error 719 ms 1048576 KB Execution killed with signal 9
4 Runtime error 714 ms 1048576 KB Execution killed with signal 9
5 Runtime error 645 ms 1048576 KB Execution killed with signal 9
6 Runtime error 1071 ms 1048576 KB Execution killed with signal 9
7 Correct 57 ms 77904 KB Output is correct
8 Correct 80 ms 103856 KB Output is correct
9 Correct 109 ms 157712 KB Output is correct
10 Correct 19 ms 26448 KB Output is correct
11 Correct 15 ms 19280 KB Output is correct
12 Correct 309 ms 474440 KB Output is correct
13 Runtime error 663 ms 1048576 KB Execution killed with signal 9
14 Runtime error 652 ms 1048576 KB Execution killed with signal 9
15 Runtime error 667 ms 1048576 KB Execution killed with signal 9
16 Runtime error 646 ms 1048576 KB Execution killed with signal 9
17 Runtime error 705 ms 1048576 KB Execution killed with signal 9
18 Runtime error 580 ms 1048576 KB Execution killed with signal 9
19 Runtime error 734 ms 1048576 KB Execution killed with signal 9
20 Runtime error 700 ms 1048576 KB Execution killed with signal 9
21 Runtime error 642 ms 1048576 KB Execution killed with signal 9
22 Runtime error 673 ms 1048576 KB Execution killed with signal 9
23 Runtime error 682 ms 1048576 KB Execution killed with signal 9
24 Runtime error 659 ms 1048576 KB Execution killed with signal 9
25 Runtime error 804 ms 1048576 KB Execution killed with signal 9
26 Correct 1082 ms 863624 KB Output is correct
27 Runtime error 1000 ms 1048576 KB Execution killed with signal 9
28 Runtime error 996 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1174 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1145 ms 1048576 KB Execution killed with signal 9
31 Runtime error 962 ms 1048576 KB Execution killed with signal 9
32 Runtime error 1080 ms 1048576 KB Execution killed with signal 9