oj.uz

Submission #1020404

# Submission time Handle Problem Language Result Execution time Memory
1020404 2024-07-12T03:54:06 Z NguyenPhucThang Tracks in the Snow (BOI13_tracks) C++14
19.375 / 100
 663 ms 177060 KB 
#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int base = 31;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
const int N = 4005;

char a[N][N];
int comp[N][N], dis[N * N], cnt = 0;
int dx[] = {0, 1, 0, -1},
   dy[] ={1, 0, -1, 0};

vector<int> g[N];
map<pii, bool> con;

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
  
   int m, n;
   cin >> m >> n;
   forr(i, 1, m) forr(j, 1, n) cin >> a[i][j];

   forr(i, 1, n){
      forr(j, 1, n){
         if (!comp[i][j] && a[i][j] != '.'){
            comp[i][j] = ++cnt;
            queue<pii> q;
            q.push({i, j});
            while (!q.empty()){
               pii u = q.front();
               q.pop();
               forr(k, 0, 3){
                  int nx = u.fi + dx[k], ny = u.se + dy[k];
                  if (1 <= nx && nx <= m && 1 <= ny && ny <= n && a[nx][ny] == a[i][j] && !comp[nx][ny]){
                     q.push({nx, ny});
                     comp[nx][ny] = comp[i][j];
                  } 
               }
            }
         }
      }
   }

   forr(i, 1, n){
      forr(j, 1, n){
         forr(k, 0, 3){
            int nx = i + dx[k], ny = j + dy[k];
            if (1 <= nx && nx <= m && 1 <= ny && ny <= n && comp[i][j] && comp[nx][ny]){
               if (comp[i][j] != comp[nx][ny] && !con[{comp[i][j], comp[nx][ny]}]){
                  int u = comp[i][j], v = comp[nx][ny];
                  g[u].pb(v);
                  g[v].pb(u);
                  con[{u, v}] = con[{v, u}] = true;
               }
            }
         }
      }
   }

   dis[1] = 1;
   queue<int> q;
   q.push(1);
   int res = 0;
   while (!q.empty()){
      int u = q.front();
      q.pop();
      res = max(res, dis[u]);
      for(int v : g[u]){
         if (!dis[v]) {
            dis[v] = dis[u] + 1;
            q.push(v);
         }
      }
   }

   cout << res;



   return 0;
}

Subtask #1
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 17232 KB Execution killed with signal 6
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 10 ms 7676 KB Output is correct
5 Runtime error 13 ms 9564 KB Execution killed with signal 6
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 3128 KB Output is correct
10 Runtime error 13 ms 9052 KB Execution killed with signal 6
11 Correct 4 ms 3676 KB Output is correct
12 Runtime error 19 ms 10240 KB Execution killed with signal 6
13 Runtime error 13 ms 9560 KB Execution killed with signal 6
14 Runtime error 13 ms 9564 KB Execution killed with signal 6
15 Runtime error 25 ms 16732 KB Execution killed with signal 6
16 Runtime error 28 ms 17404 KB Execution killed with signal 6
17 Runtime error 22 ms 16656 KB Execution killed with signal 6
18 Correct 10 ms 7516 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 31064 KB Output isn't correct
2 Runtime error 64 ms 33104 KB Execution killed with signal 6
3 Runtime error 342 ms 134420 KB Execution killed with signal 6
4 Runtime error 113 ms 68256 KB Execution killed with signal 6
5 Runtime error 306 ms 102008 KB Execution killed with signal 6
6 Runtime error 662 ms 176992 KB Execution killed with signal 6
7 Incorrect 9 ms 32616 KB Output isn't correct
8 Incorrect 10 ms 31080 KB Output isn't correct
9 Runtime error 576 ms 130944 KB Execution killed with signal 6
10 Correct 586 ms 65384 KB Output is correct
11 Incorrect 9 ms 32088 KB Output isn't correct
12 Runtime error 9 ms 7772 KB Execution killed with signal 6
13 Runtime error 67 ms 33060 KB Execution killed with signal 6
14 Runtime error 43 ms 24208 KB Execution killed with signal 6
15 Runtime error 48 ms 31628 KB Execution killed with signal 6
16 Runtime error 113 ms 38756 KB Execution killed with signal 6
17 Runtime error 136 ms 56872 KB Execution killed with signal 6
18 Runtime error 132 ms 70496 KB Execution killed with signal 6
19 Runtime error 112 ms 68192 KB Execution killed with signal 6
20 Runtime error 111 ms 57440 KB Execution killed with signal 6
21 Runtime error 213 ms 101792 KB Execution killed with signal 6
22 Runtime error 299 ms 101724 KB Execution killed with signal 6
23 Runtime error 297 ms 102240 KB Execution killed with signal 6
24 Runtime error 241 ms 95584 KB Execution killed with signal 6
25 Runtime error 510 ms 176480 KB Execution killed with signal 6
26 Correct 418 ms 81952 KB Output is correct
27 Runtime error 517 ms 176820 KB Execution killed with signal 6
28 Runtime error 640 ms 177060 KB Execution killed with signal 6
29 Runtime error 663 ms 176764 KB Execution killed with signal 6
30 Runtime error 581 ms 175956 KB Execution killed with signal 6
31 Runtime error 516 ms 143444 KB Execution killed with signal 6
32 Runtime error 497 ms 176724 KB Execution killed with signal 6