oj.uz

답안 #535461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535461 2022-03-10T09:58:30 Z dozer Tracks in the Snow (BOI13_tracks) C++14
80.3125 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#define fastio() ios_base::sync_with_stdio(0), cin.tie(0);
#define pb push_back
#define ll long long
#define sp " "
#define endl "\n"
#define modulo 100000007
#define N 20000005
#define st first
#define nd second
//#define int long long
#define pii pair<int, int>
 
vector<int> adj[N];
int id[4005][4005], arr[4015][4005], col[N], dist[N];
unordered_map<char, int> value;
 
 
int32_t main()
{
	fastio();

 
 
	//cout<<(((4005 * 4005 * 2) + 6 * N) * 4)/ (1<<20)<<endl;
	int h, w;
	cin>>h>>w;
 
	value['F'] = 1, value['R'] = 2, value['.'] = 3;
	int ctr = 1;
 
	for (int i = 1; i <= h; i++)
	{
		for (int j = 1; j <= w; j++)
		{
			char tmp;
			cin>>tmp;
			switch(tmp)
			{
				case 'F':
					arr[i][j] = 1;
					break;
				case 'R':
					arr[i][j] = 2;
					break;
				case '.':
					arr[i][j] = 3;
					break;
			}
			//arr[i][j] = value[tmp];
			id[i][j] = ctr;
			col[id[i][j]] = arr[i][j];
			ctr++;
		}
	}
 
	for (int i = 1; i <= h; i++)
	{
		for (int j = 1; j <= w; j++)
		{
			if (arr[i][j] == 3) continue;
			int color = arr[i][j];
			if (i < h && arr[i + 1][j] != 3) 
			{
				adj[id[i][j]].pb(id[i + 1][j]);
				adj[id[i + 1][j]].pb(id[i][j]);
			}
			if (j < w && arr[i][j + 1] != 3) 
			{
				adj[id[i][j]].pb(id[i][j + 1]);
				adj[id[i][j + 1]].pb(id[i][j]);
			}
		}
	}
 
	int color = col[1], ans = 0;
 
	deque<int> q;
	memset(dist, modulo, sizeof(dist));
 
	q.push_front(1);
	dist[1] = 1;
 
	int steps = 0;
	while(!q.empty())
	{
		steps++;
		int top = q.front();
		q.pop_front();
		ans = max(ans, dist[top]);
		for (int k = 0; k < adj[top].size(); k++)
		{
			int curr = adj[top][k];
			int d = ((col[top] == col[curr]) ? 0 : 1);
			if (d == 0 && dist[curr] > dist[top]) 
			{
				dist[curr] = dist[top];
				q.push_front(curr);
			}
			else if (dist[curr] > dist[top] + 1)
			{
				dist[curr] = dist[top] + 1;
				q.push_back(curr);
			}
		}
	}
 
	//cout<<steps<<endl;
	cout<<ans<<endl;
	cerr<<"time taken : "<<(float) clock() / CLOCKS_PER_SEC<<" seconds\n";
	return 0;
}

Compilation message

tracks.cpp: In function 'int32_t main()':
tracks.cpp:64:8: warning: unused variable 'color' [-Wunused-variable]
   64 |    int color = arr[i][j];
      |        ^~~~~
tracks.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (int k = 0; k < adj[top].size(); k++)
      |                   ~~^~~~~~~~~~~~~~~~~
tracks.cpp:78:6: warning: unused variable 'color' [-Wunused-variable]
   78 |  int color = col[1], ans = 0;
      |      ^~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 331 ms 562584 KB Output is correct
2 Correct 287 ms 548440 KB Output is correct
3 Correct 278 ms 548700 KB Output is correct
4 Correct 314 ms 559052 KB Output is correct
5 Correct 291 ms 552176 KB Output is correct
6 Correct 272 ms 548448 KB Output is correct
7 Correct 272 ms 548728 KB Output is correct
8 Correct 279 ms 548964 KB Output is correct
9 Correct 263 ms 549232 KB Output is correct
10 Correct 291 ms 551872 KB Output is correct
11 Correct 316 ms 551548 KB Output is correct
12 Correct 312 ms 554200 KB Output is correct
13 Correct 304 ms 552164 KB Output is correct
14 Correct 303 ms 552232 KB Output is correct
15 Correct 346 ms 561164 KB Output is correct
16 Correct 362 ms 562636 KB Output is correct
17 Correct 328 ms 558484 KB Output is correct
18 Correct 329 ms 559088 KB Output is correct

Subtask #2
50.3125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 580024 KB Output is correct
2 Correct 418 ms 598616 KB Output is correct
3 Correct 1245 ms 858316 KB Output is correct
4 Correct 627 ms 627600 KB Output is correct
5 Correct 985 ms 820700 KB Output is correct
6 Runtime error 1907 ms 1048576 KB Execution killed with signal 9
7 Correct 328 ms 581320 KB Output is correct
8 Correct 305 ms 580104 KB Output is correct
9 Correct 328 ms 549896 KB Output is correct
10 Correct 339 ms 548896 KB Output is correct
11 Correct 312 ms 580684 KB Output is correct
12 Correct 327 ms 550016 KB Output is correct
13 Correct 422 ms 597704 KB Output is correct
14 Correct 388 ms 578616 KB Output is correct
15 Correct 372 ms 577508 KB Output is correct
16 Correct 378 ms 570656 KB Output is correct
17 Correct 693 ms 664404 KB Output is correct
18 Correct 643 ms 646480 KB Output is correct
19 Correct 540 ms 626092 KB Output is correct
20 Correct 504 ms 631276 KB Output is correct
21 Correct 841 ms 754268 KB Output is correct
22 Correct 903 ms 819144 KB Output is correct
23 Correct 1049 ms 759584 KB Output is correct
24 Correct 790 ms 774888 KB Output is correct
25 Execution timed out 2136 ms 879912 KB Time limit exceeded
26 Runtime error 1724 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1821 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1772 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1746 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1682 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2146 ms 1008864 KB Time limit exceeded
32 Runtime error 1674 ms 1048576 KB Execution killed with signal 9