oj.uz

Submission #438706

# Submission time Handle Problem Language Result Execution time Memory
438706 2021-06-28T14:02:04 Z O_o Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1112 ms 239608 KB 
#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;
    		}
    		if(a[x1][y1] == '.')
    		{
    			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)
    	{
    		if(a[i][j] != '.')
    		{
    			ans= max(ans, dist[i][j]);
    		}
    	}
    }
    cout<<ans;

    return 0;
}

Compilation message

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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 126148 KB Output is correct
2 Correct 69 ms 125420 KB Output is correct
3 Correct 66 ms 125508 KB Output is correct
4 Correct 74 ms 126284 KB Output is correct
5 Correct 69 ms 125712 KB Output is correct
6 Correct 66 ms 125492 KB Output is correct
7 Correct 71 ms 125540 KB Output is correct
8 Correct 72 ms 125524 KB Output is correct
9 Correct 72 ms 125564 KB Output is correct
10 Correct 73 ms 125604 KB Output is correct
11 Correct 76 ms 125752 KB Output is correct
12 Correct 71 ms 125776 KB Output is correct
13 Correct 70 ms 125660 KB Output is correct
14 Correct 69 ms 125636 KB Output is correct
15 Correct 81 ms 126064 KB Output is correct
16 Correct 78 ms 126064 KB Output is correct
17 Correct 76 ms 126016 KB Output is correct
18 Correct 92 ms 126248 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 125644 KB Output is correct
2 Correct 107 ms 127940 KB Output is correct
3 Correct 256 ms 144752 KB Output is correct
4 Correct 135 ms 130116 KB Output is correct
5 Correct 174 ms 136424 KB Output is correct
6 Correct 960 ms 173080 KB Output is correct
7 Correct 70 ms 125628 KB Output is correct
8 Correct 71 ms 125704 KB Output is correct
9 Correct 68 ms 125636 KB Output is correct
10 Correct 68 ms 125632 KB Output is correct
11 Correct 71 ms 125696 KB Output is correct
12 Correct 68 ms 125580 KB Output is correct
13 Correct 103 ms 127684 KB Output is correct
14 Correct 88 ms 126988 KB Output is correct
15 Correct 89 ms 127052 KB Output is correct
16 Correct 87 ms 126776 KB Output is correct
17 Correct 168 ms 130468 KB Output is correct
18 Correct 137 ms 130228 KB Output is correct
19 Correct 144 ms 130116 KB Output is correct
20 Correct 115 ms 129808 KB Output is correct
21 Correct 177 ms 136644 KB Output is correct
22 Correct 189 ms 136052 KB Output is correct
23 Correct 275 ms 134352 KB Output is correct
24 Correct 166 ms 135868 KB Output is correct
25 Correct 604 ms 143684 KB Output is correct
26 Correct 1112 ms 239608 KB Output is correct
27 Correct 922 ms 194732 KB Output is correct
28 Correct 902 ms 172172 KB Output is correct
29 Correct 897 ms 166780 KB Output is correct
30 Correct 988 ms 180532 KB Output is correct
31 Correct 672 ms 137836 KB Output is correct
32 Correct 970 ms 191548 KB Output is correct