oj.uz

답안 #1094771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094771 2024-09-30T13:44:02 Z laithalnaimi Tracks in the Snow (BOI13_tracks) C++17
58.8542 / 100
 457 ms 130944 KB 
// [ الأحزاب: 56] ﴿ إِنَّ اللَّهَ وَمَلَائِكَتَهُ يُصَلُّونَ عَلَى النَّبِيِّ ۚ يَا أَيُّهَا الَّذِينَ آمَنُوا صَلُّوا عَلَيْهِ وَسَلِّمُوا تَسْلِيمًا﴾
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <deque>
#include <iomanip> 
#define mem(a, b) memset(a, b, sizeof a);
#define db(x) cout << #x << ": " << (x) << "\n";
#define coutfloat(n,d)     cout << fixed << setprecision(d) << n << endl //#include <iomanip> 
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pss pair<string , string>
#define fv(vec) for(auto &v : vec)
#define cinv(v,n) vector<int>v(n);for(int i = 0 ; i <n ; i++)cin>>v[i];
#define cinvll(v,n) vector<ll>v(n);for(ll i = 0 ; i <n ; i++)cin>>v[i];
#define fi(n) for(int i = 0 ; i < n ; i++)
#define fj(n) for(int j = 0 ; j < n ; j++)
#define feq(n) for(int eq = 0 ; eq <= n ; eq++)
#define pb push_back
#define mp make_pair
#define ll long long 
#define ini in<int>()
#define inl in<ll>()
#define inc in<char>()
#define inb in<bool>()
#define ins in<string>()
#define test int T;cin>>T;while(T--)
#define yes  cout<<"YES\n"
#define no  cout<<"NO\n"
#define LAITH ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define file freopen("knapsack.in", "r", stdin);freopen("knapsack.out", "w", stdout);
using namespace std;
 
template <typename T>
T in() { T x; cin >> x; return x; }

int meadow[4004][4004];
string snow[4004];
int n, m , ans = 1,dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};
bool chk(int x, int y){
  return (x >= 0 && x <m && y >= 0 && y < n && snow[x][y] != '.');
}
void BFS(){
  deque<pii> q;
  q.push_front({0,0});
  meadow[0][0] = 1;
  while(!q.empty()){
    pii point = q.front();
    q.pop_front();
    ans = max(ans, meadow[point.first][point.second]);
    fi(4){
      int x = point.first + dx[i], y = point.second + dy[i];
      if(chk(x, y) && !meadow[x][y])
        snow[x][y] == snow[point.first][point.second] ?
          (meadow[x][y] = meadow[point.first][point.second],q.push_front({x,y})):
          (meadow[x][y] = meadow[point.first][point.second] + 1,q.push_back({x,y}));
    }
  }
}
void solve(){
  n = ini , m = ini;
  fi(n)cin >> snow[i];
  BFS();
  cout <<ans;
}
int main() {
    LAITH;
    solve();
    return 0;
}

Subtask #1
21.6666666667 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4068 KB Output isn't correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 4 ms 2820 KB Output isn't correct
5 Correct 2 ms 1948 KB Output is correct
6 Correct 0 ms 596 KB Output is correct
7 Correct 1 ms 608 KB Output is correct
8 Incorrect 1 ms 856 KB Output isn't correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1624 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 4 ms 2200 KB Output is correct
13 Correct 2 ms 2136 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 12 ms 3676 KB Output is correct
16 Incorrect 8 ms 3932 KB Output isn't correct
17 Correct 6 ms 3928 KB Output is correct
18 Incorrect 6 ms 2652 KB Output isn't correct

Subtask #2
37.1875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Correct 27 ms 11808 KB Output is correct
3 Correct 158 ms 75632 KB Output is correct
4 Incorrect 53 ms 29788 KB Output isn't correct
5 Correct 103 ms 51532 KB Output is correct
6 Correct 434 ms 109904 KB Output is correct
7 Incorrect 1 ms 608 KB Output isn't correct
8 Incorrect 1 ms 608 KB Output isn't correct
9 Incorrect 1 ms 616 KB Output isn't correct
10 Incorrect 0 ms 616 KB Output isn't correct
11 Incorrect 1 ms 616 KB Output isn't correct
12 Correct 1 ms 1160 KB Output is correct
13 Correct 39 ms 12012 KB Output is correct
14 Incorrect 24 ms 8544 KB Output isn't correct
15 Correct 11 ms 10344 KB Output is correct
16 Incorrect 2 ms 2148 KB Output isn't correct
17 Correct 65 ms 28740 KB Output is correct
18 Correct 51 ms 32132 KB Output is correct
19 Incorrect 47 ms 29928 KB Output isn't correct
20 Incorrect 7 ms 7504 KB Output isn't correct
21 Incorrect 80 ms 49944 KB Output isn't correct
22 Correct 78 ms 51384 KB Output is correct
23 Incorrect 95 ms 36140 KB Output isn't correct
24 Incorrect 88 ms 46836 KB Output isn't correct
25 Correct 231 ms 96348 KB Output is correct
26 Correct 296 ms 130944 KB Output is correct
27 Correct 378 ms 123064 KB Output is correct
28 Correct 454 ms 110060 KB Output is correct
29 Correct 457 ms 108492 KB Output is correct
30 Correct 392 ms 113620 KB Output is correct
31 Incorrect 319 ms 72232 KB Output isn't correct
32 Correct 299 ms 108264 KB Output is correct