답안 #969830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969830	2024-04-25T16:13:58 Z	starchan	Tracks in the Snow (BOI13_tracks)	C++17	62.7083 / 100	538 ms	128236 KB

tracks

#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pf push_front
#define pb push_back
#define pob pop_back
#define pof pop_front
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int LMX = 2e7;
const int INF = 1e5;

char g[LMX]; int n, m;
vector<int> d(LMX, INF);

signed main()
{
	fast();
	cin >> n >> m;
	vector<int> dt = {+m, -m, +1, -1}; 
	for(int i = 0; i < m*n; i++)
		cin >> g[i];
	deque<int> pq;
	pq.pf(0); d[0] = 0;
	while(pq.size())
	{
		int u = pq.front(); pq.pof();
		for(auto x: dt)
		{
			int v = u+x;
			if(v < 0 || (v >= (n*m)) || (g[v] == '.'))
				continue;
			int cn = (g[u] != g[v]); 
			if(d[v] > (d[u]+cn))
			{
				d[v] = d[u]+cn;
				if(cn)
					pq.pb(v);
				else
					pq.pf(v);
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n*m; i++)
	{
		if(g[i] != '.')
			ans = max(ans, ++d[i]);
	}
	cout << ans << "\n";
	return 0;
}	

Subtask #1

23.3333333333 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	24 ms	81072 KB	Output isn't correct
2	Correct	17 ms	78948 KB	Output is correct
3	Correct	16 ms	78836 KB	Output is correct
4	Correct	20 ms	78936 KB	Output is correct
5	Correct	18 ms	78680 KB	Output is correct
6	Correct	15 ms	78680 KB	Output is correct
7	Correct	16 ms	78524 KB	Output is correct
8	Incorrect	15 ms	78680 KB	Output isn't correct
9	Correct	16 ms	78684 KB	Output is correct
10	Correct	18 ms	78688 KB	Output is correct
11	Correct	18 ms	78684 KB	Output is correct
12	Incorrect	19 ms	78940 KB	Output isn't correct
13	Correct	17 ms	78684 KB	Output is correct
14	Correct	17 ms	78684 KB	Output is correct
15	Correct	24 ms	81112 KB	Output is correct
16	Incorrect	24 ms	80976 KB	Output isn't correct
17	Correct	22 ms	80988 KB	Output is correct
18	Correct	20 ms	78940 KB	Output is correct

Subtask #2

39.375 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	16 ms	78680 KB	Output isn't correct
2	Correct	49 ms	82396 KB	Output is correct
3	Incorrect	188 ms	110932 KB	Output isn't correct
4	Correct	79 ms	86620 KB	Output is correct
5	Incorrect	219 ms	97876 KB	Output isn't correct
6	Correct	497 ms	118100 KB	Output is correct
7	Incorrect	16 ms	78752 KB	Output isn't correct
8	Incorrect	16 ms	78684 KB	Output isn't correct
9	Correct	17 ms	79104 KB	Output is correct
10	Correct	17 ms	78684 KB	Output is correct
11	Correct	17 ms	78728 KB	Output is correct
12	Correct	16 ms	78680 KB	Output is correct
13	Correct	51 ms	82260 KB	Output is correct
14	Correct	35 ms	81756 KB	Output is correct
15	Incorrect	30 ms	81808 KB	Output isn't correct
16	Correct	31 ms	81496 KB	Output is correct
17	Correct	97 ms	86964 KB	Output is correct
18	Incorrect	63 ms	86712 KB	Output isn't correct
19	Correct	81 ms	86448 KB	Output is correct
20	Incorrect	66 ms	86356 KB	Output isn't correct
21	Incorrect	125 ms	98356 KB	Output isn't correct
22	Incorrect	219 ms	97872 KB	Output isn't correct
23	Correct	179 ms	94520 KB	Output is correct
24	Incorrect	158 ms	97872 KB	Output isn't correct
25	Incorrect	186 ms	110776 KB	Output isn't correct
26	Correct	295 ms	128236 KB	Output is correct
27	Correct	388 ms	121788 KB	Output is correct
28	Correct	538 ms	117968 KB	Output is correct
29	Incorrect	516 ms	117576 KB	Output isn't correct
30	Correct	458 ms	119880 KB	Output is correct
31	Incorrect	389 ms	99380 KB	Output isn't correct
32	Correct	387 ms	126072 KB	Output is correct