oj.uz

Submission #653105

# Submission time Handle Problem Language Result Execution time Memory
653105 2022-10-25T17:44:20 Z pauloamed Tracks in the Snow (BOI13_tracks) C++14
25.2083 / 100
 2000 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 4010;

int n, m; 
string M[MAXN];
int id[MAXN][MAXN];
int curr_id;

bool ok(int i, int j){
  if(i < 0 || j < 0 || i >= n || j >= m) return false;
  return M[i][j] != '.';
}

int DI[] = {0, 0, -1, 1};
int DJ[] = {-1, 1, 0, 0};

set<int> v[MAXN * MAXN];

int solve(int x, int p){
  int ans = 0;
  for(auto y : v[x]) if(y != p){
    ans = max(ans, solve(y, x));
  }
  return ans + 1;
}

int32_t main(){
  cin.tie(NULL)->sync_with_stdio(false);
  cin >> n >> m;
  for(int i = 0; i < n; ++i){
    cin >> M[i];
  }

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(id[i][j] == 0 && ok(i, j)){
        queue<pair<int,int>> q;
        q.push({i, j});
        id[i][j] = ++curr_id;
        while(q.size()){
          auto [x, y] = q.front();
          q.pop();

          for(int k = 0; k < 4; ++k){
            int ni = x + DI[k];
            int nj = y + DJ[k];
            if(ok(ni, nj) && id[ni][nj] == 0 && M[ni][nj] == M[i][j]){
              id[ni][nj] = id[x][y];
              q.push({ni, nj});
            }
          }
        }
      }
    }
  }

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(ok(i, j)){
        for(int k = 0; k < 4; ++k){
          int ni = i + DI[k];
          int nj = j + DJ[k];
          if(ok(ni, nj) && M[ni][nj] != M[i][j]){
            v[id[i][j]].insert(id[ni][nj]);
          }
        }
      }
    }
  }

  cout << solve(1, -1) << "\n";

}

Compilation message

tracks.cpp: In function 'int32_t main()':
tracks.cpp:43:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |           auto [x, y] = q.front();
      |                ^

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 458 ms 1048576 KB Execution killed with signal 9
2 Correct 340 ms 755752 KB Output is correct
3 Runtime error 427 ms 1048576 KB Execution killed with signal 9
4 Runtime error 474 ms 1048576 KB Execution killed with signal 9
5 Runtime error 450 ms 1048576 KB Execution killed with signal 9
6 Correct 331 ms 755660 KB Output is correct
7 Runtime error 424 ms 1048576 KB Execution killed with signal 9
8 Runtime error 421 ms 1048576 KB Execution killed with signal 9
9 Runtime error 439 ms 1048576 KB Execution killed with signal 9
10 Runtime error 418 ms 1048576 KB Execution killed with signal 9
11 Runtime error 1096 ms 1048576 KB Execution killed with signal 9
12 Runtime error 448 ms 1048576 KB Execution killed with signal 9
13 Runtime error 445 ms 1048576 KB Execution killed with signal 9
14 Runtime error 431 ms 1048576 KB Execution killed with signal 9
15 Runtime error 487 ms 1048576 KB Execution killed with signal 9
16 Runtime error 466 ms 1048576 KB Execution killed with signal 9
17 Runtime error 458 ms 1048576 KB Execution killed with signal 9
18 Runtime error 466 ms 1048576 KB Execution killed with signal 9

Subtask #2
21.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 771892 KB Output is correct
2 Runtime error 513 ms 1048576 KB Execution killed with signal 9
3 Runtime error 880 ms 1048576 KB Execution killed with signal 9
4 Runtime error 535 ms 1048576 KB Execution killed with signal 9
5 Runtime error 877 ms 1048576 KB Execution killed with signal 9
6 Runtime error 1723 ms 1048576 KB Execution killed with signal 9
7 Correct 341 ms 772428 KB Output is correct
8 Correct 338 ms 771876 KB Output is correct
9 Runtime error 608 ms 1048576 KB Execution killed with signal 9
10 Correct 362 ms 756008 KB Output is correct
11 Execution timed out 2126 ms 786504 KB Time limit exceeded
12 Correct 340 ms 758104 KB Output is correct
13 Runtime error 527 ms 1048576 KB Execution killed with signal 9
14 Runtime error 476 ms 1048576 KB Execution killed with signal 9
15 Correct 415 ms 784616 KB Output is correct
16 Runtime error 477 ms 1048576 KB Execution killed with signal 9
17 Runtime error 636 ms 1048576 KB Execution killed with signal 9
18 Correct 663 ms 861064 KB Output is correct
19 Runtime error 518 ms 1048576 KB Execution killed with signal 9
20 Runtime error 564 ms 1048576 KB Execution killed with signal 9
21 Runtime error 1706 ms 1048576 KB Execution killed with signal 9
22 Runtime error 982 ms 1048576 KB Execution killed with signal 9
23 Runtime error 825 ms 1048576 KB Execution killed with signal 9
24 Correct 849 ms 1004700 KB Output is correct
25 Runtime error 973 ms 1048576 KB Execution killed with signal 9
26 Correct 958 ms 823964 KB Output is correct
27 Correct 1151 ms 837836 KB Output is correct
28 Runtime error 1801 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1662 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1561 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2025 ms 1048576 KB Time limit exceeded
32 Runtime error 1094 ms 1048576 KB Execution killed with signal 9