Submission #369570

#	Time	Username	Problem	Language	Result	Execution time	Memory
369570		ijxjdjd	Tracks in the Snow (BOI13_tracks)	C++14	75.94 / 100	2113 ms	508232 KiB

tracks

#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;
}

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