Submission #163556

#	Time	Username	Problem	Language	Result	Execution time	Memory
163556		Ort	Tracks in the Snow (BOI13_tracks)	C++11	78.13 / 100	2156 ms	1045332 KiB

tracks

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define MAX 4005
 
using namespace std;
using namespace __gnu_pbds;
 
int dy[4] = {0, 1, -1, 0};
int dx[4] = {1, 0, 0, -1};
 
char mat[MAX][MAX];
int comp[MAX][MAX];
bool visited[MAX][MAX], vis[MAX*MAX];
vector<int> adj[MAX*MAX];
int n, m, sol;

bool isvalid(int y,int x) {return y>0 && x>0 && y<=n && x<=m && mat[y][x]!='.';}
 
void flood(int y, int x, int num, char c) {
	if(!isvalid(y, x) || visited[y][x] || mat[y][x]!=c) return;
	visited[y][x] = 1; comp[y][x] = num;
	for(int i=0;i<4;i++) flood(y+dy[i], x+dx[i], num, c);
}

struct chash {int operator()(pair<int,int> x) const { return x.first* 31 + x.second; }};
gp_hash_table<pair<int,int>, bool, chash> s;

queue<pair<int,int> > q;
 
int main() {
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++) scanf("%s", mat[i]+1);
	int comp_c = 1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!visited[i][j] && isvalid(i,j)) flood(i, j, comp_c++, mat[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(mat[i][j]!='.')
				for(int k=0;k<4;k++) {
					int y = i+dy[k];
					int x = j+dx[k];
					if(!isvalid(y, x) || comp[i][j]==comp[y][x] || comp[i][j]==0 || comp[y][x]==0) continue;
					if((s.find(make_pair(comp[i][j], comp[y][x])) == s.end() )) {
						adj[comp[i][j]].push_back(comp[y][x]);
						s[make_pair(comp[i][j], comp[y][x])] = true;
					}
				}
  	vis[1] = true;
  	q.push(make_pair(1,1));
  	while(!q.empty()) {
    	pair<int,int> curr = q.front(); q.pop();
    	sol = max(sol, curr.second);
    	for(int nxt:adj[curr.first]) {
      		if(vis[nxt])continue;
      		vis[nxt] = true;
      		q.push(make_pair(nxt, curr.second+1));
    	}
  	}
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:31: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:32:29: 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", mat[i]+1);
                        ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 48.125 / 70