Submission #438704

#	Time	Username	Problem	Language	Result	Execution time	Memory
438704		O_o	Tracks in the Snow (BOI13_tracks)	C++14	19.79 / 100	1506 ms	247708 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)

#define pb push_back
#define mp make_pair
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define precise(i) fixed << setprecision(i)
#define fi first
#define se second
#define sz(x) ((int)(x).size())

#define err() cout<<"\n==================================\n";
#define errA(A) for(auto i:A) cout<<i<<" "; cout<<"\n";
#define err1(a) cout<<#a<<" "<<a<<"\n";
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<"\n";
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<"\n";
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<"\n";

const int logN = 20;
const int M = 1000000007;
const int INF = 1e12;
#define PI 3.14159265;
const int N = 200005;

#define Pii pair<int,int>
#define Vi vector<int>
#define Vpii vector<Pii>

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

int32_t main()
{
    setIO();
    int h, w;
    cin>>h>>w;
    vector<string> a(h);
    rep(i,0,h)
    {
    	cin>>a[i];
    }
    int dist[4000][4000];
    rep(i,0,4000)
    {
    	rep(j,0,4000)
    	{
    		dist[i][j]= INF;
    	}
    }
    Vpii moves(4);
    moves[0]= mp(0, 1);
    moves[1]= mp(1, 0);
    moves[2]= mp(0, -1);
    moves[3]= mp(-1, 0);
    int ans= 1;
    dist[0][0]= 1;
    deque<Pii> q;
    Pii node= mp(0, 0);
    q.push_front(node);
    while(!q.empty())
    {
    	node= q.front();
    	q.pop_front();
    	int x= node.fi;
    	int y= node.se;
    	for(auto e: moves)
    	{
    		int x1= x+e.fi;
    		int y1= y+e.se;
    		if((x1 < 0) || (x1 >= h))
    		{
    			continue;
    		}
    		if((y1 < 0) || (y1 >= w))
    		{
    			continue;
    		}
    		int w1= (int)(a[x][y] != a[x1][y1]);
    		if((dist[x][y] + w1) < dist[x1][y1])
    		{
    			dist[x1][y1]= (dist[x][y] + w1);
    			if(!w1)
    			{
    				q.push_front(mp(x1, y1));
    			}
    			else
    			{
    				q.push_back(mp(x1, y1));
    			}
    		}
    	}
    }
    rep(i,0,h)
    {
    	rep(j,0,w)
    	{
    		ans= max(ans, dist[i][j]);
    	}
    }
    cout<<ans;

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 6.666666666666667 / 30
• Subtask 2: 13.125 / 70