oj.uz

Submission #544619

# Submission time Handle Problem Language Result Execution time Memory
544619 2022-04-02T13:47:13 Z pancankes Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 574 ms 223892 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
using namespace std;
#define int long long
const int MAXN=1e5;

// very smart solution using 0/1 BFS
// answer is just the maxinum shortest path from the top left cell
// where the weight from each adjacent cell is:
// 1 when going from different animals
// 0 when going to same animal

int n, m, dist[4000][4000], ans = 1;
// instead of storing in a grid, can speed up code by storing in vector of strings!
string snow[4000];

// standard floodfill things to include, speeds up implementation
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

bool inside(int x, int y) {
    // since we dont care if snow[x][y] is a '.', since paths must be connected
	return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');
}

void setIO(string name="") { 
	ios_base::sync_with_stdio(0); cin.tie(0); 
	if (!name.empty()) {
		freopen((name+".in").c_str(), "r", stdin); 
		freopen((name+".out").c_str(), "w", stdout);
	}
}

int32_t main()
{
    setIO();
    cin >> n >> m;
    for (int i=0; i<n; i++) cin >> snow[i];

    // deque is just double ended queue
    deque<pair<int,int>> q;

    // search 0/1 BFS from top left grid
    q.push_back({0,0});

    // top left grid would have distance of 1 from itself
    dist[0][0]=1;

    while (!q.empty())
    {
        pair<int,int> c=q.front();
        q.pop_front();
        // answer is longest shortest distance from top left
        ans=max(ans,dist[c.first][c.second]);

        // search adjacent grid cells
        for (int i=0; i<4; i++)
        {
            int x=c.first+dx[i],y=c.second+dy[i];
            // dist also functions as a sort of visited array
            if (inside(x,y)&&dist[x][y]==0) 
            {
                // if adjacent cells are same, then they have distance of 0
                // therefore, 0/1 BFS, push to front of the queue
                if (snow[x][y]==snow[c.first][c.second])
                {
                    dist[x][y]=dist[c.first][c.second];
                    q.push_front({x,y});
                }
                else
                {
                    dist[x][y]=dist[c.first][c.second]+1;
                    q.push_back({x,y});
                }
            }
        }
    }
    cout << ans << endl;
}

Compilation message

tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen((name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen((name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4608 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 7 ms 4052 KB Output is correct
5 Correct 3 ms 2132 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 2 ms 1748 KB Output is correct
11 Correct 2 ms 1748 KB Output is correct
12 Correct 4 ms 2388 KB Output is correct
13 Correct 2 ms 2132 KB Output is correct
14 Correct 2 ms 2132 KB Output is correct
15 Correct 9 ms 4152 KB Output is correct
16 Correct 12 ms 4564 KB Output is correct
17 Correct 9 ms 4308 KB Output is correct
18 Correct 9 ms 4140 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15836 KB Output is correct
2 Correct 34 ms 13512 KB Output is correct
3 Correct 163 ms 77776 KB Output is correct
4 Correct 62 ms 39512 KB Output is correct
5 Correct 135 ms 60496 KB Output is correct
6 Correct 574 ms 170328 KB Output is correct
7 Correct 11 ms 16724 KB Output is correct
8 Correct 11 ms 15992 KB Output is correct
9 Correct 2 ms 900 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 11 ms 16312 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 36 ms 13808 KB Output is correct
14 Correct 23 ms 9228 KB Output is correct
15 Correct 24 ms 13368 KB Output is correct
16 Correct 17 ms 6064 KB Output is correct
17 Correct 87 ms 29140 KB Output is correct
18 Correct 71 ms 43904 KB Output is correct
19 Correct 64 ms 39592 KB Output is correct
20 Correct 48 ms 24128 KB Output is correct
21 Correct 103 ms 52044 KB Output is correct
22 Correct 136 ms 60812 KB Output is correct
23 Correct 165 ms 48908 KB Output is correct
24 Correct 101 ms 50508 KB Output is correct
25 Correct 385 ms 143404 KB Output is correct
26 Correct 342 ms 223892 KB Output is correct
27 Correct 439 ms 196792 KB Output is correct
28 Correct 542 ms 170632 KB Output is correct
29 Correct 552 ms 167620 KB Output is correct
30 Correct 510 ms 176444 KB Output is correct
31 Correct 449 ms 105680 KB Output is correct
32 Correct 380 ms 168028 KB Output is correct