oj.uz

Submission #854756

# Submission time Handle Problem Language Result Execution time Memory
854756 2023-09-28T18:53:52 Z cj03 Tracks in the Snow (BOI13_tracks) C++14
82.5 / 100
 1640 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

int a[4005][4005];
vector<pair<pair<int,int>, int>> adj[4005][4005];
int d[4005][4005];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); 
 
    int h, w; cin >> h >> w;
    memset(d, -1, sizeof(d));
    for (int i = 1; i <= h; i++) {
      for (int j = 1; j <= w; j++) {
        char c; cin >> c;
        if (c=='.') a[i][j]=1;
        if (c=='R') a[i][j]=2;
        if (c=='F') a[i][j] = 3;
      }
    }
    for (int i = 1; i <= h; i++) {
      for (int j = 1; j <= w; j++) {
        int x = a[i][j]; if (x==1) continue;
        if (i+1 <= h && a[i+1][j]!=1) adj[i][j].push_back({{i+1, j}, (x==5-a[i+1][j])});
        if (i-1 >= 1 && a[i-1][j]!=1) adj[i][j].push_back({{i-1, j}, (x==5-a[i-1][j])});
        if (j+1 <= w && a[i][j+1]!=1) adj[i][j].push_back({{i, j+1}, (x==5-a[i][j+1])});
        if (j-1 >= 1 && a[i][j-1] != 1) adj[i][j].push_back({{i, j-1}, (x==5-a[i][j-1])});
      }
    }
    d[h][w] = 1;
    deque<pair<int,int>> q;
    q.push_back({h, w});
    while (!q.empty()) {
      int i = q.front().first, j=q.front().second; 
      q.pop_front();
      for (auto p : adj[i][j]) {
        int x= p.first.first, y=p.first.second, c = p.second;
        if (d[x][y]==-1 || d[x][y] > d[i][j]+c) {
          d[x][y] = d[i][j]+c;
          if (c==0) {
            q.push_front({x, y});
          } else {
            q.push_back({x, y});
          }
        }
      }
    }
    
    int ans = 1;
    for (int i = 1; i <= h; i++) {
      for (int j = 1; j <= w; j++) {
        ans = max(ans, d[i][j]);
      }
    }
    cout << ans << endl;

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 462676 KB Output is correct
2 Correct 85 ms 441796 KB Output is correct
3 Correct 85 ms 441628 KB Output is correct
4 Correct 108 ms 457812 KB Output is correct
5 Correct 89 ms 446692 KB Output is correct
6 Correct 85 ms 441592 KB Output is correct
7 Correct 86 ms 441772 KB Output is correct
8 Correct 86 ms 442008 KB Output is correct
9 Correct 86 ms 441680 KB Output is correct
10 Correct 90 ms 445268 KB Output is correct
11 Correct 90 ms 446448 KB Output is correct
12 Correct 97 ms 450900 KB Output is correct
13 Correct 90 ms 446804 KB Output is correct
14 Correct 90 ms 446696 KB Output is correct
15 Correct 115 ms 459096 KB Output is correct
16 Correct 123 ms 462656 KB Output is correct
17 Correct 105 ms 453980 KB Output is correct
18 Correct 107 ms 457808 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 501588 KB Output is correct
2 Correct 194 ms 498004 KB Output is correct
3 Correct 665 ms 704596 KB Output is correct
4 Correct 240 ms 496980 KB Output is correct
5 Correct 563 ms 636584 KB Output is correct
6 Runtime error 981 ms 1048576 KB Execution killed with signal 9
7 Correct 96 ms 501852 KB Output is correct
8 Correct 94 ms 501568 KB Output is correct
9 Correct 92 ms 443452 KB Output is correct
10 Correct 86 ms 441936 KB Output is correct
11 Correct 92 ms 501504 KB Output is correct
12 Correct 87 ms 443984 KB Output is correct
13 Correct 198 ms 498004 KB Output is correct
14 Correct 148 ms 478032 KB Output is correct
15 Correct 144 ms 465980 KB Output is correct
16 Correct 151 ms 469056 KB Output is correct
17 Correct 364 ms 567072 KB Output is correct
18 Correct 336 ms 510900 KB Output is correct
19 Correct 241 ms 496976 KB Output is correct
20 Correct 220 ms 515920 KB Output is correct
21 Correct 437 ms 609368 KB Output is correct
22 Correct 529 ms 636384 KB Output is correct
23 Correct 600 ms 668932 KB Output is correct
24 Correct 451 ms 591716 KB Output is correct
25 Correct 1640 ms 661260 KB Output is correct
26 Runtime error 913 ms 1048576 KB Execution killed with signal 9
27 Runtime error 948 ms 1048576 KB Execution killed with signal 9
28 Runtime error 965 ms 1048576 KB Execution killed with signal 9
29 Runtime error 978 ms 1048576 KB Execution killed with signal 9
30 Runtime error 970 ms 1048576 KB Execution killed with signal 9
31 Runtime error 993 ms 1048576 KB Execution killed with signal 9
32 Runtime error 965 ms 1048576 KB Execution killed with signal 9