Submission #67026

#	Time	Username	Problem	Language	Result	Execution time	Memory
67026		RezwanArefin01	Tracks in the Snow (BOI13_tracks)	C++17	18.85 / 100	2191 ms	1049600 KiB

tracks

///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll; 
typedef pair<int, int> ii; 

const int N = 4010; 
vector<int> adj[N * N], cost[N * N]; 
char g[N][N]; 
int d[N * N], n, m; 
int dx[] = {0, 0, 1, -1}; 
int dy[] = {1, -1, 0, 0}; 

int id(int x, int y) { return x * m + y; }

void addEdge(int u, int v, int c) {
    adj[u].push_back(v);
    cost[u].push_back(c); 
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) 
        scanf(" %s", g[i]); 
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) if(g[i][j] != '.') {
            for(int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < n && y > 0 && y < m && g[x][y] != '.') {
                    int c = g[i][j] != g[x][y];
                    addEdge(id(i, j), id(x, y), c);
                }
            }
        }
    }
    deque<int> q; 
    memset(d, 63, sizeof d); 
    d[0] = 0;
    q.push_back(0);
    while(!q.empty()) {
        int u = q.front(); q.pop_front();
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i], c = cost[u][i];
            if(d[v] > d[u] + c) {
                d[v] = d[u] + c;
                if(c) q.push_back(v);
                else q.push_front(v);
            }
        }
    }
    int mx = 0;
    for(int i = 0; i < n * m; i++) {
        if(d[i] <= n * m) mx = max(mx, d[i]); 
    }
    printf("%d\n", 1 +  mx); 
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:44:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < adj[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
tracks.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", g[i]); 
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 16.666666666666668 / 30
• Subtask 2: 2.1875 / 70