oj.uz

Submission #1106728

# Submission time Handle Problem Language Result Execution time Memory
1106728 2024-10-31T01:52:07 Z polarity Tracks in the Snow (BOI13_tracks) C++17
40.8333 / 100
 1194 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 + 1, vector<int>(k + 1, 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 648 ms 1048576 KB Execution killed with signal 9
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 31 ms 39216 KB Output is correct
5 Correct 152 ms 231364 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 167 ms 246364 KB Output is correct
11 Correct 6 ms 4688 KB Output is correct
12 Correct 419 ms 598088 KB Output is correct
13 Correct 152 ms 231240 KB Output is correct
14 Correct 150 ms 231428 KB Output is correct
15 Runtime error 742 ms 1048576 KB Execution killed with signal 9
16 Runtime error 733 ms 1048576 KB Execution killed with signal 9
17 Runtime error 735 ms 1048576 KB Execution killed with signal 9
18 Correct 32 ms 39240 KB Output is correct

Subtask #2
17.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 103948 KB Output is correct
2 Runtime error 701 ms 1048576 KB Execution killed with signal 9
3 Runtime error 719 ms 1048576 KB Execution killed with signal 9
4 Runtime error 700 ms 1048576 KB Execution killed with signal 9
5 Runtime error 669 ms 1048576 KB Execution killed with signal 9
6 Runtime error 1035 ms 1048576 KB Execution killed with signal 9
7 Correct 51 ms 77944 KB Output is correct
8 Correct 67 ms 103864 KB Output is correct
9 Correct 103 ms 157512 KB Output is correct
10 Correct 17 ms 26440 KB Output is correct
11 Correct 13 ms 19280 KB Output is correct
12 Correct 298 ms 474516 KB Output is correct
13 Runtime error 665 ms 1048576 KB Execution killed with signal 9
14 Runtime error 719 ms 1048576 KB Execution killed with signal 9
15 Runtime error 701 ms 1048576 KB Execution killed with signal 9
16 Runtime error 697 ms 1048576 KB Execution killed with signal 9
17 Runtime error 764 ms 1048576 KB Execution killed with signal 9
18 Runtime error 642 ms 1048576 KB Execution killed with signal 9
19 Runtime error 714 ms 1048576 KB Execution killed with signal 9
20 Runtime error 684 ms 1048576 KB Execution killed with signal 9
21 Runtime error 652 ms 1048576 KB Execution killed with signal 9
22 Runtime error 659 ms 1048576 KB Execution killed with signal 9
23 Runtime error 687 ms 1048576 KB Execution killed with signal 9
24 Runtime error 692 ms 1048576 KB Execution killed with signal 9
25 Runtime error 800 ms 1048576 KB Execution killed with signal 9
26 Correct 1194 ms 875784 KB Output is correct
27 Runtime error 1122 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1084 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1147 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1131 ms 1048576 KB Execution killed with signal 9
31 Runtime error 963 ms 1048576 KB Execution killed with signal 9
32 Runtime error 1126 ms 1048576 KB Execution killed with signal 9