oj.uz

답안 #860821

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
860821 2023-10-14T12:14:30 Z shahi_45 Tracks in the Snow (BOI13_tracks) C++17
75.3125 / 100
 1409 ms 463816 KB 
//JAI BAJRANG BALI

#include <bits/stdc++.h>
#include <algorithm>
#include <numeric>
using namespace std;
// #ifndef ONLINE_JUDGE
// #include "./debugging.hpp" // pathname
// #else
// #define debug(...)
// #endif

#define ndl "\n"
typedef long long int ll;
typedef unsigned long long int ull;
//#define int long long
// ... Rest of your template code ...

#define out1(x) cout<<x<<"\n";
#define out(x) cout<<x<<" ";
#define vi  vector<int>
#define vll  vector<ll>
#define vs vector<string>
#define sortA(a) sort(a.begin(),a.end())
#define sortD(a) sort(a.begin(),a.end(), greater<ll>())
#define yes() std::cout << "YES\n";
#define no() std::cout << "NO\n";
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define p 998244353
using ll = long long;
vll dx={1,-1,0,0};
vll dy={0,0,-1,1};
// 1,0 -1,0 0,-1 0,1
void solve(ll tc){
   ll n,m; cin>>n>>m; vector<string> steps(n); 
   vector<vll> d(n,vll(m,0));
   for(ll i=0;i<n;i++){
    cin>>steps[i];
   } 
   d[0][0]=1;
   ll ans=1;
   deque<vll> q;
   q.push_front({0,0});
   while(!q.empty()){
    vll v1=q.front(); q.pop_front();
    ll x1=v1[0]; ll y1=v1[1];
    ans=max(ans,d[x1][y1]);
    for(ll i=0;i<4;i++){
        ll new_x=x1+dx[i];
        ll new_y=y1+dy[i];
        if(new_x>=0 and new_y>=0 and new_x<n and new_y<n and (steps[new_x][new_y]!='.')){
            ll weight=0;
            if(steps[new_x][new_y]!=steps[x1][y1]) {
                weight++;
            }
            if(d[new_x][new_y]==0){
                d[new_x][new_y]=d[x1][y1]+weight;
                if(weight==0){
                    q.push_front({new_x,new_y});
                }
                else{
                    q.push_back({new_x,new_y});
                }
            }
        }
    }
   }
   out1(ans);
   

}


signed main(){
    ll T=1;
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
   //cin>>T;
    for (ll tc = 1; tc <=T; tc++) solve(tc);
    return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Subtask #1
25.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 3224 KB Output isn't correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 11 ms 3164 KB Output is correct
5 Correct 2 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 456 KB Output isn't correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 3 ms 1112 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct
13 Correct 2 ms 1312 KB Output is correct
14 Correct 3 ms 1232 KB Output is correct
15 Correct 15 ms 2904 KB Output is correct
16 Incorrect 24 ms 3264 KB Output isn't correct
17 Correct 10 ms 2908 KB Output is correct
18 Correct 11 ms 3164 KB Output is correct

Subtask #2
50.3125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 55 ms 15868 KB Output is correct
3 Correct 306 ms 159304 KB Output is correct
4 Incorrect 69 ms 37460 KB Output isn't correct
5 Correct 211 ms 89424 KB Output is correct
6 Correct 1387 ms 250988 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 976 KB Output is correct
9 Incorrect 1 ms 860 KB Output isn't correct
10 Incorrect 1 ms 604 KB Output isn't correct
11 Correct 2 ms 1116 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 57 ms 15964 KB Output is correct
14 Incorrect 32 ms 9308 KB Output isn't correct
15 Correct 25 ms 10328 KB Output is correct
16 Incorrect 5 ms 6748 KB Output isn't correct
17 Correct 143 ms 40708 KB Output is correct
18 Correct 91 ms 39812 KB Output is correct
19 Incorrect 75 ms 37560 KB Output isn't correct
20 Incorrect 16 ms 34360 KB Output isn't correct
21 Correct 176 ms 92512 KB Output is correct
22 Correct 212 ms 89432 KB Output is correct
23 Incorrect 231 ms 77412 KB Output isn't correct
24 Correct 175 ms 90640 KB Output is correct
25 Correct 582 ms 159264 KB Output is correct
26 Correct 938 ms 463816 KB Output is correct
27 Correct 1133 ms 306748 KB Output is correct
28 Correct 1375 ms 251428 KB Output is correct
29 Correct 1409 ms 238260 KB Output is correct
30 Correct 1307 ms 267268 KB Output is correct
31 Incorrect 973 ms 105216 KB Output isn't correct
32 Correct 978 ms 246408 KB Output is correct