Submission #108132

#	Time	Username	Problem	Language	Result	Execution time	Memory
108132		wilwxk	Tracks in the Snow (BOI13_tracks)	C++11	3.33 / 100	2153 ms	1049604 KiB

tracks

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

const int MAXN=4e3+5;
char v[MAXN][MAXN];
vector<int> g[MAXN*MAXN], pes[MAXN*MAXN];
int dist[MAXN];
int n, m;

int convert(int i, int j) { if(i==0||j==0) return 0; return (i-1)*m+j; }

void liga(int i, int j, int i2, int j2){
	if(i<=0||j<=0||i>n||j>m) return;
	if(i2<=0||j2<=0||i2>n||j2>m) return;
	if(v[i][j]=='.'||v[i2][j2]=='.') return;
	int a=convert(i, j); int b=convert(i2, j2);
	g[a].push_back(b);
	int peso=0;
	if(v[i][j]!=v[i2][j2]) peso=1;
	pes[a].push_back(peso);	
	// printf("liga %d e %d - %d\n", a, b, peso);
}

void bfs() {
	memset(dist, -1, sizeof(dist));
	dist[1]=1;
	deque<int> dq;
	dq.push_back(1);
	while(!dq.empty()) {
		int cur=dq.front(); dq.pop_front();
		for(int i=0; i<g[cur].size(); i++) {
			int viz=g[cur][i]; int peso=pes[cur][i];
			if(dist[viz]!=-1) continue;
			if(peso==0) dq.push_front(viz);
			else dq.push_back(viz);
			dist[viz]=dist[cur]+peso; 
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++) scanf(" %s", &v[i][1]);
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			int cur=convert(i, j);
			liga(i, j, i-1, j);
			liga(i, j, i+1, j);
			liga(i, j, i, j-1);
			liga(i, j, i, j+1);
		}
	}
	bfs();

	int resp=1;
	for(int i=1; i<=n*m; i++) resp=max(resp, dist[i]);
	// for(int i=1; i<=n; i++) {
	// 	for(int j=1; j<=m; j++) {
	// 		printf("%d ", dist[convert(i, j)]);
	// 	}
	// 	printf("\n");
	// }
	printf("%d\n", resp);
}

Compilation message (stderr)

tracks.cpp: In function 'void bfs()':
tracks.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~
tracks.cpp: In function 'int main()':
tracks.cpp:46:8: warning: unused variable 'cur' [-Wunused-variable]
    int cur=convert(i, j);
        ^~~
tracks.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:43:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf(" %s", &v[i][1]);
                          ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 3.3333333333333335 / 30
• Subtask 2: 0 / 70