oj.uz

Submission #854758

# Submission time Handle Problem Language Result Execution time Memory
854758 2023-09-28T18:58:45 Z cj03 Tracks in the Snow (BOI13_tracks) C++14
82.5 / 100
 1680 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==h && j==w) 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 122 ms 462636 KB Output is correct
2 Correct 84 ms 441684 KB Output is correct
3 Correct 85 ms 441748 KB Output is correct
4 Correct 108 ms 457556 KB Output is correct
5 Correct 90 ms 446552 KB Output is correct
6 Correct 86 ms 441720 KB Output is correct
7 Correct 85 ms 441680 KB Output is correct
8 Correct 85 ms 441936 KB Output is correct
9 Correct 86 ms 441684 KB Output is correct
10 Correct 89 ms 445276 KB Output is correct
11 Correct 90 ms 446292 KB Output is correct
12 Correct 99 ms 451016 KB Output is correct
13 Correct 90 ms 446588 KB Output is correct
14 Correct 90 ms 446700 KB Output is correct
15 Correct 114 ms 458832 KB Output is correct
16 Correct 129 ms 462420 KB Output is correct
17 Correct 107 ms 453460 KB Output is correct
18 Correct 109 ms 457552 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 501584 KB Output is correct
2 Correct 196 ms 496308 KB Output is correct
3 Correct 657 ms 688720 KB Output is correct
4 Correct 247 ms 493396 KB Output is correct
5 Correct 567 ms 627628 KB Output is correct
6 Runtime error 989 ms 1048576 KB Execution killed with signal 9
7 Correct 93 ms 501844 KB Output is correct
8 Correct 94 ms 501588 KB Output is correct
9 Correct 89 ms 443216 KB Output is correct
10 Correct 90 ms 441968 KB Output is correct
11 Correct 92 ms 501496 KB Output is correct
12 Correct 87 ms 443988 KB Output is correct
13 Correct 197 ms 496468 KB Output is correct
14 Correct 148 ms 477264 KB Output is correct
15 Correct 149 ms 465104 KB Output is correct
16 Correct 142 ms 468308 KB Output is correct
17 Correct 357 ms 563280 KB Output is correct
18 Correct 339 ms 507204 KB Output is correct
19 Correct 244 ms 493304 KB Output is correct
20 Correct 226 ms 513012 KB Output is correct
21 Correct 437 ms 600416 KB Output is correct
22 Correct 534 ms 628016 KB Output is correct
23 Correct 617 ms 661336 KB Output is correct
24 Correct 435 ms 582960 KB Output is correct
25 Correct 1680 ms 645628 KB Output is correct
26 Runtime error 929 ms 1048576 KB Execution killed with signal 9
27 Runtime error 969 ms 1048576 KB Execution killed with signal 9
28 Runtime error 992 ms 1048576 KB Execution killed with signal 9
29 Runtime error 991 ms 1048576 KB Execution killed with signal 9
30 Runtime error 975 ms 1048576 KB Execution killed with signal 9
31 Runtime error 976 ms 1048576 KB Execution killed with signal 9
32 Runtime error 962 ms 1048576 KB Execution killed with signal 9