oj.uz

Submission #1020403

# Submission time Handle Problem Language Result Execution time Memory
1020403 2024-07-12T03:53:37 Z NguyenPhucThang Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 7 ms 628 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);
#ifndef ONLINE_JUDGE
   freopen(file".inp", "r", stdin);
   freopen(file".out", "w", stdout);
#endif
   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;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:39:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |    freopen(file".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:40:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |    freopen(file".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 604 KB Output isn't correct
2 Incorrect 4 ms 604 KB Output isn't correct
3 Incorrect 5 ms 604 KB Output isn't correct
4 Incorrect 5 ms 620 KB Output isn't correct
5 Incorrect 5 ms 604 KB Output isn't correct
6 Incorrect 5 ms 624 KB Output isn't correct
7 Incorrect 5 ms 604 KB Output isn't correct
8 Incorrect 5 ms 620 KB Output isn't correct
9 Incorrect 5 ms 604 KB Output isn't correct
10 Incorrect 5 ms 604 KB Output isn't correct
11 Incorrect 5 ms 604 KB Output isn't correct
12 Incorrect 5 ms 600 KB Output isn't correct
13 Incorrect 5 ms 600 KB Output isn't correct
14 Incorrect 5 ms 372 KB Output isn't correct
15 Incorrect 5 ms 604 KB Output isn't correct
16 Incorrect 5 ms 604 KB Output isn't correct
17 Incorrect 5 ms 604 KB Output isn't correct
18 Incorrect 5 ms 604 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 604 KB Output isn't correct
2 Incorrect 5 ms 624 KB Output isn't correct
3 Incorrect 4 ms 604 KB Output isn't correct
4 Incorrect 7 ms 604 KB Output isn't correct
5 Incorrect 5 ms 620 KB Output isn't correct
6 Incorrect 6 ms 604 KB Output isn't correct
7 Incorrect 5 ms 604 KB Output isn't correct
8 Incorrect 6 ms 604 KB Output isn't correct
9 Incorrect 5 ms 620 KB Output isn't correct
10 Incorrect 5 ms 604 KB Output isn't correct
11 Incorrect 5 ms 604 KB Output isn't correct
12 Incorrect 5 ms 620 KB Output isn't correct
13 Incorrect 5 ms 604 KB Output isn't correct
14 Incorrect 4 ms 604 KB Output isn't correct
15 Incorrect 4 ms 604 KB Output isn't correct
16 Incorrect 5 ms 604 KB Output isn't correct
17 Incorrect 5 ms 624 KB Output isn't correct
18 Incorrect 5 ms 604 KB Output isn't correct
19 Incorrect 5 ms 604 KB Output isn't correct
20 Incorrect 5 ms 616 KB Output isn't correct
21 Incorrect 7 ms 628 KB Output isn't correct
22 Incorrect 5 ms 600 KB Output isn't correct
23 Incorrect 4 ms 608 KB Output isn't correct
24 Incorrect 4 ms 604 KB Output isn't correct
25 Incorrect 5 ms 604 KB Output isn't correct
26 Incorrect 4 ms 624 KB Output isn't correct
27 Incorrect 5 ms 604 KB Output isn't correct
28 Incorrect 5 ms 600 KB Output isn't correct
29 Incorrect 5 ms 600 KB Output isn't correct
30 Incorrect 5 ms 604 KB Output isn't correct
31 Incorrect 5 ms 628 KB Output isn't correct
32 Incorrect 5 ms 604 KB Output isn't correct