oj.uz

Submission #813452

# Submission time Handle Problem Language Result Execution time Memory
813452 2023-08-07T18:07:31 Z birthdaycake Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 167900 KB 
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
 
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#define endl '\n'
#define int long long
#define mod 1000000007
using namespace std;
 
char m[4001][4001];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int dist[4001][4001];
signed main(){
    
    
    int h,w, ans = 0; cin >> h >> w;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> m[i][j];
        }
    }
    dist[0][0] = 1;
    priority_queue<pair<int,pair<int,int>>>d;
    d.push({-1,{0,0}});
    while(d.size()){
        auto x = d.top();
        ans = max(ans, x.first * -1);
        d.pop();
        for(int i = 0; i < 4; i++){
            int aa = x.second.first + dx[i], bb = x.second.second + dy[i];
            int val = dist[x.second.first][x.second.second];
            if(aa < 0 or bb < 0 or aa >= h or bb >= w) continue;
            if(m[aa][bb] == '.' or dist[aa][bb] != 0) continue;
            if(m[aa][bb] != m[x.second.first][x.second.second]) val++;
            dist[aa][bb] = val;
            d.push({-dist[aa][bb], {aa,bb}});
        }
    }
    
    cout << ans;
    
    
    
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 6540 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 30 ms 6096 KB Output is correct
5 Correct 7 ms 3156 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 7 ms 2516 KB Output is correct
11 Correct 8 ms 2496 KB Output is correct
12 Correct 21 ms 3580 KB Output is correct
13 Correct 7 ms 3156 KB Output is correct
14 Correct 7 ms 3156 KB Output is correct
15 Correct 37 ms 5940 KB Output is correct
16 Correct 47 ms 6420 KB Output is correct
17 Correct 29 ms 6000 KB Output is correct
18 Correct 31 ms 5968 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30988 KB Output is correct
2 Correct 149 ms 16716 KB Output is correct
3 Correct 836 ms 75428 KB Output is correct
4 Correct 237 ms 42728 KB Output is correct
5 Correct 404 ms 62300 KB Output is correct
6 Execution timed out 2088 ms 167900 KB Time limit exceeded
7 Correct 17 ms 32332 KB Output is correct
8 Correct 17 ms 31004 KB Output is correct
9 Correct 6 ms 836 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 15 ms 31700 KB Output is correct
12 Correct 2 ms 1620 KB Output is correct
13 Correct 147 ms 16696 KB Output is correct
14 Correct 85 ms 11596 KB Output is correct
15 Correct 50 ms 15968 KB Output is correct
16 Correct 70 ms 6632 KB Output is correct
17 Correct 386 ms 32412 KB Output is correct
18 Correct 201 ms 47296 KB Output is correct
19 Correct 227 ms 42800 KB Output is correct
20 Correct 179 ms 27028 KB Output is correct
21 Correct 488 ms 53856 KB Output is correct
22 Correct 404 ms 62284 KB Output is correct
23 Correct 739 ms 49924 KB Output is correct
24 Correct 366 ms 52564 KB Output is correct
25 Correct 960 ms 141192 KB Output is correct
26 Correct 1697 ms 123840 KB Output is correct
27 Execution timed out 2089 ms 136380 KB Time limit exceeded
28 Execution timed out 2078 ms 167784 KB Time limit exceeded
29 Execution timed out 2086 ms 151292 KB Time limit exceeded
30 Execution timed out 2078 ms 142004 KB Time limit exceeded
31 Execution timed out 2069 ms 103268 KB Time limit exceeded
32 Execution timed out 2084 ms 124188 KB Time limit exceeded