oj.uz

Submission #753750

# Submission time Handle Problem Language Result Execution time Memory
753750 2023-06-05T21:50:12 Z tiwerlol Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 166096 KB 
#include <iostream>
#include <map>
#include <climits>
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>
#include <bitset>
#include <chrono>
#include <random>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

///ofstream cout("apm.out");
///ifstream cin("apm.in");

const int MOD = 1e9+7;

int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};

int mat[4001][4001];
int D[4001][4001];

void solve()
{
    int n, m; cin >> n >> m;

    for(int z = 0; z < n; z++)
    {
        string s; cin >> s;

        for(int x = 0; x < s.size(); x++)
        {
            if(s[x]=='.') mat[z+1][x+1] = 1;
            else if(s[x]=='R') mat[z+1][x+1] = 2;
            else mat[z+1][x+1] = 3;
            D[z+1][x+1] = 0;
        }
    }

    priority_queue<pair<int, pair<int, int>>> pQ;
    pQ.push(make_pair(1, make_pair(1, 1)));
    D[1][1] = 1;
    int ans = 1;

    while(!pQ.empty())
    {
        int val = -pQ.top().first, i = pQ.top().second.first, j = pQ.top().second.second;
        pQ.pop();

        for(int k = 0; k < 4; k++)
        {
            int ki = di[k] + i, kj = dj[k] + j;

            if((ki>=1&&ki<=n&&kj>=1&&kj<=m) && !D[ki][kj] && mat[ki][kj]!=1)
            {
                D[ki][kj] = D[i][j] + (mat[i][j]!=mat[ki][kj]);
                ans = max(D[ki][kj], ans);
                pQ.push(make_pair(-D[ki][kj], make_pair(ki, kj)));
            }
        }
    }
    cout << ans;
}

int main()
{
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int tt = 1; //cin >> tt;

    while(tt--)
        solve();
}

Compilation message

tracks.cpp: In function 'void solve()':
tracks.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int x = 0; x < s.size(); x++)
      |                        ~~^~~~~~~~~~
tracks.cpp:52:13: warning: unused variable 'val' [-Wunused-variable]
   52 |         int val = -pQ.top().first, i = pQ.top().second.first, j = pQ.top().second.second;
      |             ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6576 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 31 ms 6152 KB Output is correct
5 Correct 7 ms 3412 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 6 ms 2932 KB Output is correct
11 Correct 7 ms 2388 KB Output is correct
12 Correct 16 ms 3412 KB Output is correct
13 Correct 5 ms 3412 KB Output is correct
14 Correct 5 ms 3412 KB Output is correct
15 Correct 34 ms 6732 KB Output is correct
16 Correct 53 ms 6588 KB Output is correct
17 Correct 24 ms 6228 KB Output is correct
18 Correct 36 ms 6168 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31444 KB Output is correct
2 Correct 113 ms 24228 KB Output is correct
3 Correct 357 ms 141284 KB Output is correct
4 Correct 134 ms 48460 KB Output is correct
5 Correct 162 ms 103108 KB Output is correct
6 Execution timed out 2074 ms 166056 KB Time limit exceeded
7 Correct 15 ms 32852 KB Output is correct
8 Correct 16 ms 31516 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 14 ms 32264 KB Output is correct
12 Correct 2 ms 1620 KB Output is correct
13 Correct 116 ms 24224 KB Output is correct
14 Correct 66 ms 15656 KB Output is correct
15 Correct 26 ms 17176 KB Output is correct
16 Correct 64 ms 9172 KB Output is correct
17 Correct 286 ms 52176 KB Output is correct
18 Correct 89 ms 51532 KB Output is correct
19 Correct 131 ms 48504 KB Output is correct
20 Correct 101 ms 44704 KB Output is correct
21 Correct 228 ms 106572 KB Output is correct
22 Correct 154 ms 103116 KB Output is correct
23 Correct 582 ms 86376 KB Output is correct
24 Correct 142 ms 105372 KB Output is correct
25 Correct 481 ms 141236 KB Output is correct
26 Correct 1414 ms 122100 KB Output is correct
27 Execution timed out 2097 ms 144676 KB Time limit exceeded
28 Execution timed out 2069 ms 166096 KB Time limit exceeded
29 Execution timed out 2025 ms 153752 KB Time limit exceeded
30 Execution timed out 2108 ms 151000 KB Time limit exceeded
31 Execution timed out 2052 ms 111440 KB Time limit exceeded
32 Execution timed out 2057 ms 143072 KB Time limit exceeded