제출 #369571

#제출 시각아이디문제언어결과실행 시간메모리
369571ijxjdjdTracks in the Snow (BOI13_tracks)C++14
0 / 100
1769 ms723272 KiB
#include <bits/stdc++.h> #define FR(i, N) for (int i = 0; i < int(N); i++) #define all(x) begin(x), end(x) using namespace std; using ll = long long; struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(pair<uint64_t, uint64_t> x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x.first + FIXED_RANDOM) + splitmix64(x.second+FIXED_RANDOM); } }; const int MAXN = 4000 + 5; int par[MAXN*MAXN]; int board[MAXN*MAXN]; int seen[MAXN*MAXN]; int rk[MAXN*MAXN]; int sz = 0; int dist[MAXN*MAXN]; //unordered_set<pair<int, int>, custom_hash> already; vector<vector<int>> adj; int find(int x) { if (par[x] == x) { return x; } return par[x] = find(par[x]); } void merge(int x, int y) { if (board[x] == board[y]) { int pX = find(x); int pY = find(y); if (rk[pX] < rk[pY]) { swap(pX, pY); } par[pY] = pX; } } void addEdge(int x, int y) { // if (board[x] != board[y] && board[x] >= 0 && board[y] >= 0) { // pair<int, int> pos = {board[x], board[y]}; // if (board[x] > board[y]) { // swap(pos.first, pos.second); // } // if (!already.count(pos)) { // already.insert(pos); adj[board[x]].push_back(board[y]); adj[board[y]].push_back(board[x]); // } // } } int H, W; int conv(int i, int j) { return i*W + j; } int main() { cin.tie(0); cin.sync_with_stdio(0); cin >> H >> W; W += 2; H += 2; FR(i, MAXN*MAXN) { par[i] = i; rk[i] = 1; board[i] = '.'; } FR(i, H-2) { FR(j, W-2) { char c; cin >> c; board[conv(i+1, j+1)] = c; } } for (int i = 1; i < H-1; i++) { for (int j = 1; j < W-1; j++) { merge(conv(i, j), conv(i+1, j)); merge(conv(i, j), conv(i-1, j)); merge(conv(i, j), conv(i, j+1)); merge(conv(i, j), conv(i, j-1)); } } fill(all(seen), -1); FR(i, MAXN*MAXN) { if (board[i] != '.' && par[i] == i) { seen[i] = sz++; adj.push_back({}); } } FR(i, MAXN*MAXN) { board[i] = seen[find(i)]; } for (int i = 1; i < H-1; i++) { for (int j = 1; j < W-1; j++) { addEdge(conv(i, j), conv(i+1, j)); addEdge(conv(i, j), conv(i-1, j)); addEdge(conv(i, j), conv(i, j+1)); addEdge(conv(i, j), conv(i, j-1)); } } fill(all(dist), MAXN*MAXN); deque<int> p; p.push_back(board[conv(1, 1)]); dist[board[conv(1, 1)]] = 0; int mx = 0; while (p.size() > 0) { int next = p.front(); p.pop_front(); for (int e : adj[next]) { if (dist[e] > dist[next] + 1) { dist[e] = dist[next]+1; p.push_back(e); mx = max(dist[e], mx); } } } cout << mx + 1 << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...