Submission #256249

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
256249	2020-08-02T12:10:02 Z	shayan_p	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1179 ms	107400 KB

tracks

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 4010, mod = 1e9 + 7, inf = 1e9 + 10;

int n, m;
string s[maxn];
int a[maxn][maxn];
bool mark[maxn][maxn];

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
    
    cin >> n >> m;
    for(int i = 0; i < n; i++){
	cin >> s[i];	
    }
    assert(s[0][0] == s[n-1][m-1] && s[0][0] != '.');
    char c = s[0][0];
    for(int i = 0; i < n; i++){
	for(int j = 0; j < m; j++){
	    a[i][j] = (s[i][j] == '.' ? -1 : (s[i][j] != c));
	}
    }
    queue<pii> q[2];
    q[0].push({0,0});
    mark[0][0] = 1;
    int ans = 0;
    while(sz(q[ans & 1])){
	while(sz(q[ans & 1])){
	    pii p = q[ans & 1].front();
	    q[ans & 1].pop();
	    for(int i = 0; i < 4; i++){
		int x = p.F + dx[i], y = p.S + dy[i];
		if(x >= 0 && y >= 0 && x < n && y < m && a[x][y] != -1 && mark[x][y] == 0)
		    mark[x][y] = 1, q[a[x][y]].push({x, y});
	    }
	}
	ans++;
    }
    return cout << ans << endl, 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	5888 KB	Output is correct
2	Correct	1 ms	640 KB	Output is correct
3	Correct	1 ms	896 KB	Output is correct
4	Correct	8 ms	5376 KB	Output is correct
5	Correct	4 ms	3200 KB	Output is correct
6	Correct	1 ms	640 KB	Output is correct
7	Correct	1 ms	896 KB	Output is correct
8	Correct	1 ms	1032 KB	Output is correct
9	Correct	1 ms	1280 KB	Output is correct
10	Correct	3 ms	2816 KB	Output is correct
11	Correct	3 ms	2304 KB	Output is correct
12	Correct	6 ms	3328 KB	Output is correct
13	Correct	4 ms	3200 KB	Output is correct
14	Correct	3 ms	3200 KB	Output is correct
15	Correct	12 ms	5888 KB	Output is correct
16	Correct	13 ms	5888 KB	Output is correct
17	Correct	11 ms	5632 KB	Output is correct
18	Correct	9 ms	5376 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	31104 KB	Output is correct
2	Correct	54 ms	18688 KB	Output is correct
3	Correct	216 ms	97272 KB	Output is correct
4	Correct	83 ms	34552 KB	Output is correct
5	Correct	173 ms	69496 KB	Output is correct
6	Correct	1179 ms	107272 KB	Output is correct
7	Correct	21 ms	32512 KB	Output is correct
8	Correct	19 ms	31104 KB	Output is correct
9	Correct	2 ms	896 KB	Output is correct
10	Correct	1 ms	640 KB	Output is correct
11	Correct	21 ms	31872 KB	Output is correct
12	Correct	2 ms	1792 KB	Output is correct
13	Correct	64 ms	18688 KB	Output is correct
14	Correct	30 ms	12672 KB	Output is correct
15	Correct	29 ms	13824 KB	Output is correct
16	Correct	22 ms	7296 KB	Output is correct
17	Correct	151 ms	37148 KB	Output is correct
18	Correct	105 ms	36728 KB	Output is correct
19	Correct	88 ms	34552 KB	Output is correct
20	Correct	56 ms	32000 KB	Output is correct
21	Correct	135 ms	71800 KB	Output is correct
22	Correct	179 ms	69496 KB	Output is correct
23	Correct	295 ms	58488 KB	Output is correct
24	Correct	137 ms	71032 KB	Output is correct
25	Correct	480 ms	97272 KB	Output is correct
26	Correct	789 ms	83144 KB	Output is correct
27	Correct	951 ms	98936 KB	Output is correct
28	Correct	1133 ms	107400 KB	Output is correct
29	Correct	1083 ms	105868 KB	Output is correct
30	Correct	1016 ms	103184 KB	Output is correct
31	Correct	788 ms	75256 KB	Output is correct
32	Correct	916 ms	98048 KB	Output is correct