Submission #813416

# Submission time Handle Problem Language Result Execution time Memory
813416 2023-08-07T17:37:40 Z birthdaycake Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
2000 ms 168308 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[i][j] = 1e18;
        }
    }
    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] * -1;
            if(aa < 0 or bb < 0 or aa >= h or bb >= w) continue;
            if(m[aa][bb] == '.') continue;
            if(m[aa][bb] != m[x.second.first][x.second.second]) val++;
            if(val < dist[aa][bb]){
                dist[aa][bb] = val;
                d.push({-dist[aa][bb], {aa,bb}});
            }
        }
    }
    
    cout << ans;
    
    
    
}
# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 6832 KB Output isn't correct
2 Incorrect 0 ms 468 KB Output isn't correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Incorrect 31 ms 6064 KB Output isn't correct
5 Incorrect 7 ms 3392 KB Output isn't correct
6 Incorrect 1 ms 468 KB Output isn't correct
7 Incorrect 1 ms 724 KB Output isn't correct
8 Incorrect 2 ms 852 KB Output isn't correct
9 Incorrect 1 ms 1108 KB Output isn't correct
10 Incorrect 7 ms 2900 KB Output isn't correct
11 Incorrect 8 ms 2388 KB Output isn't correct
12 Incorrect 20 ms 3668 KB Output isn't correct
13 Incorrect 7 ms 3412 KB Output isn't correct
14 Incorrect 7 ms 3412 KB Output isn't correct
15 Incorrect 44 ms 6924 KB Output isn't correct
16 Incorrect 55 ms 6812 KB Output isn't correct
17 Incorrect 29 ms 6664 KB Output isn't correct
18 Incorrect 31 ms 6016 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 31060 KB Output isn't correct
2 Incorrect 156 ms 24500 KB Output isn't correct
3 Incorrect 924 ms 146892 KB Output isn't correct
4 Incorrect 243 ms 47580 KB Output isn't correct
5 Incorrect 405 ms 100004 KB Output isn't correct
6 Execution timed out 2071 ms 168308 KB Time limit exceeded
7 Incorrect 15 ms 32448 KB Output isn't correct
8 Incorrect 20 ms 31032 KB Output isn't correct
9 Incorrect 8 ms 980 KB Output isn't correct
10 Incorrect 2 ms 596 KB Output isn't correct
11 Incorrect 14 ms 31896 KB Output isn't correct
12 Incorrect 2 ms 1620 KB Output isn't correct
13 Incorrect 154 ms 24500 KB Output isn't correct
14 Incorrect 89 ms 15916 KB Output isn't correct
15 Incorrect 48 ms 16924 KB Output isn't correct
16 Incorrect 79 ms 9624 KB Output isn't correct
17 Incorrect 378 ms 51404 KB Output isn't correct
18 Incorrect 198 ms 49984 KB Output isn't correct
19 Incorrect 237 ms 47592 KB Output isn't correct
20 Incorrect 215 ms 43776 KB Output isn't correct
21 Incorrect 544 ms 103368 KB Output isn't correct
22 Incorrect 412 ms 99896 KB Output isn't correct
23 Incorrect 737 ms 87164 KB Output isn't correct
24 Incorrect 391 ms 101464 KB Output isn't correct
25 Incorrect 996 ms 146520 KB Output isn't correct
26 Correct 1549 ms 126196 KB Output is correct
27 Execution timed out 2084 ms 145136 KB Time limit exceeded
28 Execution timed out 2067 ms 168228 KB Time limit exceeded
29 Execution timed out 2081 ms 168184 KB Time limit exceeded
30 Execution timed out 2037 ms 153116 KB Time limit exceeded
31 Execution timed out 2017 ms 123800 KB Time limit exceeded
32 Execution timed out 2048 ms 146648 KB Time limit exceeded