Submission #678357

#	Time	Username	Problem	Language	Result	Execution time	Memory
678357		omikron123	Tracks in the Snow (BOI13_tracks)	C++14	21.56 / 100	1056 ms	176492 KiB

tracks

// https://oj.uz/problem/view/BOI13_tracks

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;

// n,m <= 4000
int h, w;
char s[4005][4005];
int c[4005][4005];
set<int> adj[4005];
queue<pair<int,int>> q;

void floodfill(int i, int j, char t, int co) {
    q.push({i,j});
    while (!q.empty()) {
        tie(i, j) = q.front();
        q.pop();
        if (i < 0 || i >= h || j < 0 || j >= w || c[i][j]) continue;
        if (s[i][j] != t) continue;
        c[i][j] = co;
        q.push({i+1,j});
        q.push({i-1,j});
        q.push({i,j+1});
        q.push({i,j-1});
    }
}

void link(int i, int j, int p, int q) {
    if (p < 0 || p >= h || q < 0 || q >= w) return;
    if (s[i][j] == '.' || s[p][q] == '.') return;
    int c1 = c[i][j], c2 = c[p][q];
    if (c1 == c2) return;
    adj[c1].insert(c2);
    adj[c2].insert(c1);
}

queue<pair<int,int>> Q;
vector<int> d;

int main() {
    scanf("%d %d", &h, &w);
    for (int i = 0; i < h; i++)
        scanf("%s", s[i]);
    int co = 1;
    // floodfill
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            if (s[i][j] != '.' && c[i][j] == 0) {
                floodfill(i, j, s[i][j], co++);
            }
        }
    // link the nodes
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            link(i,j,i+1,j);
            link(i,j,i-1,j);
            link(i,j,i,j+1);
            link(i,j,i,j-1);
        }
    // bfs to find depth from (1,1)
    Q.push({c[0][0],1});
    d.resize(co);
    for (int i = 0; i < co; i++)
        d[i] = 0;
    int ans = 0;
    while (!Q.empty()) {
        int u = Q.front().first;
        int dep = Q.front().second;
        Q.pop();
        if (d[u]) continue;
        d[u] = dep;
        ans = max(ans, dep);
        for (int v: adj[u]) {
            Q.push({v, dep+1});
        }
    }
    printf("%d", ans);

    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d %d", &h, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%s", s[i]);
      |         ~~~~~^~~~~~~~~~~~

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