oj.uz

답안 #520304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520304 2022-01-29T09:11:11 Z PikaQ Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1118 ms 194988 KB 
#include<bits/stdc++.h>
// #define int ll
#define forn(i,n) for(int i=0;i<(n);i++)
#define Forn(i,n) for(int i=1;i<=(n);i++)
#define For(i, a, b) for (int i = a; i <= b; i++)
#define foR(i, a, b) for (int i = a; i >= b; i--)
#define ll long long
#define pb push_back
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define vi vector<int>
#define vl vector<long long>
#define vpi vector<pair<int,int> >
#define pii pair<int,int>
#define pll pair<long long,long long>
#define mp make_pair
#define all(p) p.begin(),p.end()
#define alr(p,q) p+1,p+q+1
#define ull unsigned long long
#define st0(p) memset((p),0,sizeof(p))
#define T(x) ((x)%2 ? s[(x)/2] : '.')
#define lowb(x) x&-x
#define sz(x) (x).size()
#define rz resize
#define printv(x) {for(auto &i : x) {cout << i << ' ';}cout <<'\n';}
using namespace std;
 
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
 
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
// template <class T> int max(T a, T ... b) { cout << a << " "; debug(b...);}
const int INF = 1e9+7;
const int mod = 1e9+7;
const int N = 4e3+9;
const int C = 35;
const double eps = 1e-7;

int n,m;
int d[N][N];
char c[N][N];

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool vis[N][N];


bool inside(int x,int y){
  return !(x < 0 || y < 0 || x >= n || y >= m || c[x][y] == '.');
}

void solve(){
  cin >> n >> m;
  forn(i,n) forn(j,m) cin >> c[i][j];
  deque<pii> dq;
  dq.pb({0,0});
  int ans = 0;
  while(!dq.empty()){
    pii cur = dq.front();dq.pop_front();
    vis[cur.F][cur.S] = 1;
    forn(i,4){
      int nx = cur.F + dx[i],ny = cur.S + dy[i];
      if(inside(nx,ny) && !vis[nx][ny] ){
        // debug(nx,ny);
        if(c[nx][ny] == c[cur.F][cur.S]) {
          d[nx][ny] = d[cur.F][cur.S];
          dq.push_front({nx,ny});
        }else{
          d[nx][ny] = d[cur.F][cur.S] +1;
          dq.push_back({nx,ny});
        }
      }
    }
    ans = max(ans,d[cur.F][cur.S]);
  }
  cout << ans+1 << '\n';
}   

signed main(){
  // USACO("248");
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);

  // cout << "?";
    // cout << fixed << setprecision(15);
    solve();
  return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 7408 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 824 KB Output is correct
4 Correct 14 ms 7232 KB Output is correct
5 Correct 5 ms 4044 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 4 ms 3392 KB Output is correct
11 Correct 4 ms 2992 KB Output is correct
12 Correct 9 ms 4256 KB Output is correct
13 Correct 4 ms 4044 KB Output is correct
14 Correct 5 ms 4036 KB Output is correct
15 Correct 20 ms 7272 KB Output is correct
16 Correct 23 ms 7428 KB Output is correct
17 Correct 15 ms 7116 KB Output is correct
18 Correct 14 ms 7344 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 45816 KB Output is correct
2 Correct 72 ms 20032 KB Output is correct
3 Correct 398 ms 89196 KB Output is correct
4 Correct 106 ms 40004 KB Output is correct
5 Correct 235 ms 65372 KB Output is correct
6 Correct 1094 ms 142456 KB Output is correct
7 Correct 21 ms 47948 KB Output is correct
8 Correct 22 ms 45884 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 22 ms 46916 KB Output is correct
12 Correct 2 ms 2124 KB Output is correct
13 Correct 71 ms 20032 KB Output is correct
14 Correct 43 ms 13972 KB Output is correct
15 Correct 39 ms 16984 KB Output is correct
16 Correct 33 ms 7224 KB Output is correct
17 Correct 177 ms 36712 KB Output is correct
18 Correct 115 ms 43516 KB Output is correct
19 Correct 105 ms 40064 KB Output is correct
20 Correct 105 ms 32456 KB Output is correct
21 Correct 240 ms 64724 KB Output is correct
22 Correct 235 ms 65088 KB Output is correct
23 Correct 329 ms 53476 KB Output is correct
24 Correct 201 ms 61936 KB Output is correct
25 Correct 502 ms 110056 KB Output is correct
26 Correct 672 ms 194988 KB Output is correct
27 Correct 890 ms 163608 KB Output is correct
28 Correct 1118 ms 142372 KB Output is correct
29 Correct 1074 ms 140656 KB Output is correct
30 Correct 1006 ms 151412 KB Output is correct
31 Correct 904 ms 86988 KB Output is correct
32 Correct 831 ms 157324 KB Output is correct