Submission #511193

#	Time	Username	Problem	Language	Result	Execution time	Memory
511193		DragosC1	Tracks in the Snow (BOI13_tracks)	C++17	62.81 / 100	2113 ms	786444 KiB

tracks

#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;
 
vector<vector<int>> a;
char mat[4001][4001];
map<pair<int, int>, int> mp;
bool viz[16000001];
queue<pair<int, int>> Q;
 
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
int n, m;
int l;
int Max;
 
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1}; 
 
bool inside(int i, int j) {
    if (i >= 1 && i <= n && j >= 1 && j <= m)
        return 1;
    return 0;
}
 
void dfs1(int i, int j) {
    int k, inou, jnou;
    mp[{i, j}] = l;
    for (k = 0; k < 4; k++) {
        inou = i + di[k], jnou = j + dj[k];
        if (inside(inou, jnou) && mp.find({inou, jnou}) == mp.end() && mat[inou][jnou] == mat[i][j])
            dfs1(inou, jnou);
    }
}
 
void dfs2(int i, int j) {
    int k, inou, jnou, comp1, comp2;
    viz[(i - 1) * m + j] = 1;
    for (k = 0; k < 4; k++) {
        inou = i + di[k], jnou = j + dj[k];
        comp1 = mp[{i, j}], comp2 = mp[{inou, jnou}];
        if (inside(inou, jnou) && !viz[(inou - 1) * m + jnou] && mat[inou][jnou] == mat[i][j])
            dfs2(inou, jnou);
        else if (inside(inou, jnou) && !viz[(inou - 1) * m + jnou] && mat[inou][jnou] != '.' && (a[comp1].size() == 0 || a[comp1].back() != comp2)) {
            a[comp1].emplace_back(comp2);
            a[comp2].emplace_back(comp1);
        }
    }
}
 
void bfs(int x) {
    int i;
    pair<int, int> p;
    Q.push({x, 1});
    viz[x] = 1;
    while (!Q.empty()) {
        p = Q.front();
        Q.pop();
        if (p.second > Max)
            Max = p.second;
        for (int y : a[p.first]) {
            if (!viz[y]) {
                viz[y] = 1;
                Q.push({y, p.second + 1});
            }
        }   
    }
}
 
int main() {
    fast
    int i, j;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            cin >> mat[i][j];
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (mp.find({i, j}) == mp.end() && mat[i][j] != '.') {
                l++;
                dfs1(i, j);
            }
    a.resize(l + 1);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (!viz[(i - 1) * m + j] && mat[i][j] != '.') 
                dfs2(i, j);
    for (i = 1; i <= l; i++)
        viz[i] = 0;
    bfs(1);
    cout << Max;
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void bfs(int)':
tracks.cpp:54:9: warning: unused variable 'i' [-Wunused-variable]
   54 |     int i;
      |         ^

• Subtask 1: 30 / 30
• Subtask 2: 32.8125 / 70