Submission #152832

#	Time	Username	Problem	Language	Result	Execution time	Memory
152832		Vlatko	Tracks in the Snow (BOI13_tracks)	C++14	15.31 / 100	2109 ms	656264 KiB

tracks

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

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 4001;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int R, C;
char grid[maxn][maxn];

inline bool in(int r, int c) {
	return r >= 0 && r < R && c >= 0 && c < C;
}

int numcc;
int ccid[maxn][maxn];
vector<vector<int>> adj;

void dfs(int r, int c) {
	char was = grid[r][c];
	grid[r][c] = '.';
	ccid[r][c] = numcc;
	for (int d = 0; d < 4; ++d) {
		int r1 = r + dr[d], c1 = c + dc[d];
		if (in(r1, c1) && grid[r1][c1] == was) {
			dfs(r1, c1);
		}
	}
}

int maxd;
bitset<maxn*maxn> visited;

void dfs2(int u, int d) {
	maxd = max(maxd, d);
	visited[u] = true;
	for (int v : adj[u]) {
		if (visited[v] == false) {
			dfs2(v, d+1);
		}
	}
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> R >> C;
    for (int r = 0; r < R; ++r) {
		for (int c = 0; c < C; ++c) {
			cin >> grid[r][c];
		}
	}
	numcc = 0;
	for (int r = 0; r < R; ++r) {
		for (int c = 0; c < C; ++c) {
			if (grid[r][c] != '.') {
				dfs(r, c);
				++numcc;
			}
		}
	}
	adj.resize(numcc);
	for (int r = 0; r < R; ++r) {
		for (int c = 0; c < C; ++c) {
			for (int d = 0; d < 4; ++d) {
				int r1 = r + dr[d], c1= c + dc[d];
				if (in(r1, c1) && ccid[r1][c1] != ccid[r][c]) {
					adj[ccid[r][c]].push_back(ccid[r1][c1]);
					adj[ccid[r1][c1]].push_back(ccid[r][c]);
				}
			}
		}
	}
	maxd = 0;
	dfs2(0, 0);
	cout << maxd+1 << endl;
}

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