Submission #80327

#	Time	Username	Problem	Language	Result	Execution time	Memory
80327		xiaowuc1	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	773 ms	308440 KiB

tracks

#include <bits/stdc++.h>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);

ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;

const double PI = 2 * acos(0);

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;

int r, c;
char g[4005][4005];
int dp[4005][4005];
pii q[4005*4005*2];
int dx[4]{-1, 1, 0, 0};
int dy[4]{0, 0, -1, 1};
int main() {
  scanf("%d%d\n", &r, &c);
  for(int i = 0; i < r; i++) {
    scanf("%s", g[i]);
    for(int j = 0; j < c; j++) {
      dp[i][j] = 1 << 25;
    }
  }
  dp[0][0] = 1;
  int ql = 4005*4005;
  int qr = 4005*4005;
  q[qr++] = {0, 0};
  int ret = 1;
  while(ql < qr) {
    pii curr = q[ql++];
    ret = dp[curr.first][curr.second];
    for(int k = 0; k < 4; k++) {
      int nx = curr.first + dx[k];
      int ny = curr.second + dy[k];
      if(nx < 0 || nx >= r || ny < 0 || ny >= c || g[nx][ny] == '.') continue;
      int nd = ret;
      if(g[nx][ny] != g[curr.first][curr.second]) {
        nd++;
      }
      if(nd < dp[nx][ny]) {
        dp[nx][ny] = nd;
        if(ret == nd) q[--ql] = {nx, ny};
        else q[qr++] = {nx, ny};
      }
    }
  }
  printf("%d\n", ret);
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d\n", &r, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~
tracks.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", g[i]);
     ~~~~~^~~~~~~~~~~~

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