oj.uz

Submission #534892

# Submission time Handle Problem Language Result Execution time Memory
534892 2022-03-09T05:53:23 Z aadit_ambadkar Tracks in the Snow (BOI13_tracks) C++17
82.5 / 100
 2000 ms 119184 KB 
/*
    This code belongs to Aadit Ambadkar
    Date: 2022-03-07 21:34:47
    Problem: tis
*/
#include <bits/stdc++.h>
using namespace::std;
 
typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define FF first
#define SS second
 
int n, m;
int board[4005][4005];
bool vis[4005][4005];
 
int main() {
    fastio;
    cin >> n >> m;
    F0R(i, n) {
        string s;
        cin >> s;
        F0R(j, m) {
            if (s[j]=='F') board[i][j]=1;
            else if (s[j]=='R') board[i][j]=2;
            else board[i][j]=0;
            vis[i][j]=false;
        }
    }
    // F0R(i, n) {
    //     F0R(j, m) {
    //         cout << board[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    // cout << "\n";
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    pq.push({1, {0, 0}});
    int ans = 0;
    while (!pq.empty()) {
        auto p = pq.top(); pq.pop();
        int g = p.FF, u = p.SS.FF, v = p.SS.SS;
        if (vis[u][v]) continue;
        // cout << u << " " << v << " " << g << "\n";
        ans = max(ans, g);
        vis[u][v]=true;
        if (u < n-1 && !vis[u+1][v] && board[u+1][v]!=0) pq.push({g+((board[u][v]==board[u+1][v]) ? 0 : 1), {u+1, v}});
        if (u > 0 && !vis[u-1][v] && board[u-1][v]!=0) pq.push({g+((board[u][v]==board[u-1][v]) ? 0 : 1), {u-1, v}});
        if (v < m-1 && !vis[u][v+1] && board[u][v+1]!=0) pq.push({g+((board[u][v]==board[u][v+1]) ? 0 : 1), {u, v+1}});
        if (v > 0 && !vis[u][v-1] && board[u][v-1]!=0) pq.push({g+((board[u][v]==board[u][v-1]) ? 0 : 1), {u, v-1}});
        // cout << "\n";
    }
    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 5636 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 704 KB Output is correct
4 Correct 54 ms 5384 KB Output is correct
5 Correct 7 ms 3020 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 3 ms 844 KB Output is correct
9 Correct 1 ms 1096 KB Output is correct
10 Correct 7 ms 2636 KB Output is correct
11 Correct 13 ms 2248 KB Output is correct
12 Correct 31 ms 3148 KB Output is correct
13 Correct 6 ms 3020 KB Output is correct
14 Correct 6 ms 3016 KB Output is correct
15 Correct 60 ms 5672 KB Output is correct
16 Correct 98 ms 5644 KB Output is correct
17 Correct 35 ms 5312 KB Output is correct
18 Correct 54 ms 5520 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 30796 KB Output is correct
2 Correct 175 ms 17976 KB Output is correct
3 Correct 471 ms 94456 KB Output is correct
4 Correct 130 ms 33736 KB Output is correct
5 Correct 144 ms 67912 KB Output is correct
6 Execution timed out 2095 ms 119184 KB Time limit exceeded
7 Correct 14 ms 32204 KB Output is correct
8 Correct 18 ms 30896 KB Output is correct
9 Correct 8 ms 720 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 16 ms 31676 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 174 ms 17992 KB Output is correct
14 Correct 95 ms 11972 KB Output is correct
15 Correct 22 ms 13124 KB Output is correct
16 Correct 95 ms 6704 KB Output is correct
17 Correct 485 ms 36420 KB Output is correct
18 Correct 78 ms 35652 KB Output is correct
19 Correct 130 ms 33652 KB Output is correct
20 Correct 131 ms 31064 KB Output is correct
21 Correct 292 ms 70208 KB Output is correct
22 Correct 151 ms 67920 KB Output is correct
23 Correct 855 ms 57192 KB Output is correct
24 Correct 133 ms 69436 KB Output is correct
25 Correct 404 ms 94452 KB Output is correct
26 Execution timed out 2033 ms 80852 KB Time limit exceeded
27 Execution timed out 2031 ms 92828 KB Time limit exceeded
28 Execution timed out 2049 ms 114252 KB Time limit exceeded
29 Execution timed out 2104 ms 115364 KB Time limit exceeded
30 Execution timed out 2066 ms 113696 KB Time limit exceeded
31 Execution timed out 2108 ms 74696 KB Time limit exceeded
32 Execution timed out 2093 ms 93604 KB Time limit exceeded