oj.uz

Submission #1020425

# Submission time Handle Problem Language Result Execution time Memory
1020425 2024-07-12T04:19:04 Z NguyenPhucThang Tracks in the Snow (BOI13_tracks) C++14
75.9375 / 100
 2000 ms 1048576 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 * 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 390484 KB Output is correct
2 Correct 162 ms 377428 KB Output is correct
3 Correct 158 ms 377428 KB Output is correct
4 Correct 180 ms 382032 KB Output is correct
5 Correct 180 ms 381008 KB Output is correct
6 Correct 154 ms 377060 KB Output is correct
7 Correct 187 ms 377428 KB Output is correct
8 Correct 157 ms 377936 KB Output is correct
9 Correct 165 ms 377912 KB Output is correct
10 Correct 169 ms 380660 KB Output is correct
11 Correct 161 ms 378964 KB Output is correct
12 Correct 193 ms 383056 KB Output is correct
13 Correct 170 ms 381012 KB Output is correct
14 Correct 174 ms 381012 KB Output is correct
15 Correct 234 ms 389456 KB Output is correct
16 Correct 232 ms 390480 KB Output is correct
17 Correct 214 ms 388952 KB Output is correct
18 Correct 168 ms 382036 KB Output is correct

Subtask #2
45.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 407400 KB Output isn't correct
2 Correct 399 ms 428132 KB Output is correct
3 Correct 1615 ms 699936 KB Output is correct
4 Correct 532 ms 454600 KB Output is correct
5 Execution timed out 2089 ms 1048576 KB Time limit exceeded
6 Correct 2000 ms 564168 KB Output is correct
7 Incorrect 212 ms 408760 KB Output isn't correct
8 Incorrect 170 ms 407296 KB Output isn't correct
9 Correct 874 ms 439636 KB Output is correct
10 Correct 791 ms 440228 KB Output is correct
11 Incorrect 171 ms 408148 KB Output isn't correct
12 Correct 165 ms 380172 KB Output is correct
13 Correct 408 ms 428120 KB Output is correct
14 Correct 298 ms 409172 KB Output is correct
15 Correct 338 ms 412740 KB Output is correct
16 Correct 356 ms 412304 KB Output is correct
17 Correct 817 ms 499884 KB Output is correct
18 Correct 844 ms 500828 KB Output is correct
19 Correct 513 ms 454752 KB Output is correct
20 Correct 505 ms 461708 KB Output is correct
21 Incorrect 1010 ms 573024 KB Output isn't correct
22 Execution timed out 2064 ms 928072 KB Time limit exceeded
23 Correct 1467 ms 612624 KB Output is correct
24 Incorrect 1122 ms 650380 KB Output isn't correct
25 Execution timed out 2065 ms 750972 KB Time limit exceeded
26 Correct 654 ms 457556 KB Output is correct
27 Correct 822 ms 473940 KB Output is correct
28 Execution timed out 2060 ms 564180 KB Time limit exceeded
29 Correct 1718 ms 525748 KB Output is correct
30 Correct 1423 ms 509852 KB Output is correct
31 Execution timed out 2057 ms 619856 KB Time limit exceeded
32 Correct 868 ms 493396 KB Output is correct