Submission #163535

#	Time	Username	Problem	Language	Result	Execution time	Memory
163535		Ort	Tracks in the Snow (BOI13_tracks)	C++11	0 / 100	2159 ms	1048580 KiB

tracks

#include<bits/stdc++.h>
#define MAX 4005
 
using namespace std;
 
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];
int siz[MAX*MAX], link[MAX*MAX];
vector<int> adj[MAX*MAX];
int n, m, sol;
 
int find(int x) {
	if(x==link[x]) return x;
	return link[x] = find(link[x]);
}
	
void unite(int a, int b) {
	a = find(a); b = find(b);
	if(a==b) return;
	if(siz[a] < siz[b]) swap(a,b);
	siz[a] += siz[b];
	link[b] = a;
}
 
void flood(int y, int x, int num, char c) {
	if(y<=0 || x<=0 || y>n || x>m || mat[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);
}
 
void dfs(int s, int p, int depth) {
	for(int u:adj[s]) if(u!=p) dfs(u, s, depth+1);
	sol = max(sol, depth);
}
 
int main() {
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++) scanf("%s", mat[i]+1);
	for(int i=1;i<=n*m;i++) link[i] = i, siz[i] = 1;
	int comp_c = 1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!visited[i][j] && mat[i][j]!='.') {
				flood(i, j, comp_c, mat[i][j]);
				comp_c++;
			}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++)
			cout << comp[i][j];
		cout << endl;
	}
	
	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(y<=0 || x<=0 || y>n || x>m || mat[y][x]=='.') continue;
					if(find(comp[y][x])!=find(comp[i][j])) {
						unite(comp[y][x], comp[i][j]);
						adj[comp[y][x]].push_back(comp[i][j]);
						adj[comp[i][j]].push_back(comp[y][x]);
					}
				}
	dfs(1, -1, 1);
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:41: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:42: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: 0 / 30
• Subtask 2: 0 / 70