oj.uz

Submission #854757

# Submission time Handle Problem Language Result Execution time Memory
854757 2023-09-28T18:56:18 Z cj03 Tracks in the Snow (BOI13_tracks) C++14
82.5 / 100
 1748 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[1][1] = 1;
    deque<pair<int,int>> q;
    q.push_back({1, 1});
    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 123 ms 462416 KB Output is correct
2 Correct 88 ms 441552 KB Output is correct
3 Correct 88 ms 441940 KB Output is correct
4 Correct 109 ms 457584 KB Output is correct
5 Correct 91 ms 446744 KB Output is correct
6 Correct 85 ms 441684 KB Output is correct
7 Correct 89 ms 441852 KB Output is correct
8 Correct 87 ms 441936 KB Output is correct
9 Correct 85 ms 441816 KB Output is correct
10 Correct 88 ms 445268 KB Output is correct
11 Correct 90 ms 446292 KB Output is correct
12 Correct 100 ms 450836 KB Output is correct
13 Correct 91 ms 446668 KB Output is correct
14 Correct 90 ms 446688 KB Output is correct
15 Correct 114 ms 458832 KB Output is correct
16 Correct 132 ms 462572 KB Output is correct
17 Correct 106 ms 453428 KB Output is correct
18 Correct 107 ms 457556 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 501732 KB Output is correct
2 Correct 199 ms 496720 KB Output is correct
3 Correct 664 ms 688828 KB Output is correct
4 Correct 246 ms 493392 KB Output is correct
5 Correct 539 ms 627556 KB Output is correct
6 Runtime error 1066 ms 1048576 KB Execution killed with signal 9
7 Correct 92 ms 501844 KB Output is correct
8 Correct 96 ms 501588 KB Output is correct
9 Correct 90 ms 443220 KB Output is correct
10 Correct 86 ms 441832 KB Output is correct
11 Correct 93 ms 501408 KB Output is correct
12 Correct 87 ms 443984 KB Output is correct
13 Correct 200 ms 496388 KB Output is correct
14 Correct 149 ms 477264 KB Output is correct
15 Correct 147 ms 464980 KB Output is correct
16 Correct 143 ms 468548 KB Output is correct
17 Correct 365 ms 563252 KB Output is correct
18 Correct 339 ms 506964 KB Output is correct
19 Correct 245 ms 493420 KB Output is correct
20 Correct 229 ms 512592 KB Output is correct
21 Correct 443 ms 600512 KB Output is correct
22 Correct 546 ms 627792 KB Output is correct
23 Correct 631 ms 661336 KB Output is correct
24 Correct 455 ms 582740 KB Output is correct
25 Correct 1748 ms 645496 KB Output is correct
26 Runtime error 999 ms 1048576 KB Execution killed with signal 9
27 Runtime error 972 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1059 ms 1048576 KB Execution killed with signal 9
29 Runtime error 998 ms 1048576 KB Execution killed with signal 9
30 Runtime error 997 ms 1048576 KB Execution killed with signal 9
31 Runtime error 1018 ms 1048576 KB Execution killed with signal 9
32 Runtime error 1012 ms 1048576 KB Execution killed with signal 9