Submission #1138541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138541		chrls	Tracks in the Snow (BOI13_tracks)	C++17	19.38 / 100	944 ms	1114112 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

constexpr int INF = 1000000;
constexpr int MAXN = 4000;
int grid[MAXN][MAXN];
vector<vector<int>> component (MAXN, vector<int>(MAXN, -1));
set<int> adj[MAXN];
int num_components = 0;
int R, C;

void dfs(int r, int c, int num){
    component[r][c] = num;
    if(r>0){
        if(grid[r-1][c] == grid[r][c] && component[r-1][c] == -1){
            dfs(r-1, c, num);
        }
        if(grid[r-1][c] != grid[r][c] && component[r-1][c] != -1){
            adj[num].insert(component[r-1][c]);
            adj[component[r-1][c]].insert(num);
        }

    }
    if(r<R-1){
        if(grid[r+1][c] == grid[r][c] && component[r+1][c] == -1){
            dfs(r+1, c, num);
        }
        if(grid[r+1][c] != grid[r][c] && component[r+1][c] != -1){
            adj[num].insert(component[r+1][c]);
            adj[component[r+1][c]].insert(num);
        }
    }
    if(c>0){
        if(grid[r][c-1] == grid[r][c] && component[r][c-1] == -1){
            dfs(r, c-1, num);
        }
        if(grid[r][c-1] != grid[r][c] && component[r][c-1] != -1){
            adj[num].insert(component[r][c-1]);
            adj[component[r][c-1]].insert(num);
        }
    }
    if(c<C-1){
        if(grid[r][c+1] == grid[r][c] && component[r][c+1] == -1){
            dfs(r, c+1, num);
        }
        if(grid[r][c+1] != grid[r][c] && component[r][c+1] != -1){
            adj[num].insert(component[r][c+1]);
            adj[component[r][c+1]].insert(num);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> R >> C;
    char a;
    for(int r = 0; r != R; ++r){
        for(int c = 0; c != C; ++c){
            cin >> a;
            if(a == '.') { grid[r][c] = 0; }
            if(a == 'R') { grid[r][c] = 1; }
            if(a == 'F') { grid[r][c] = 2; }
        }
    }

    for(int r = 0; r != R; ++r){
        for(int c = 0; c != C; ++c){
            if(component[r][c] != -1) continue;
            if(grid[r][c] == 0) continue;
            dfs(r, c, num_components);
            num_components++;
        }
    }

    //bfs
    vector<int> visited(num_components, INF);
    queue<int> q;
    q.push(0);
    visited[0] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        //process node
        for(int e : adj[x]){
            if(visited[e] != INF) continue;
            q.push(e);
            visited[e] = visited[x] + 1;
        }
    }

    int result = 0;
    for(int i = 0; i < num_components; ++i){
        result = max(result, visited[i]);
    }

    cout << result;

    return 0;
}

• Subtask 1: 15 / 30
• Subtask 2: 4.375 / 70