CF 1651D Nearest Excluded Points

题目描述

http://codeforces.com/contest/1651/problem/D

简要题意：给定 $n$ 个点，对于每个点求一个离它最近且不是给定点的点，距离是曼哈顿距离

$n\le 2\times 10^5,x_i,y_i\le 2\times 10^5$

Solution

注意到答案的点一定是距某个给定点为 $1$ 的点，我们把这些点都加进来跑多关键点最短路即可

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <tuple>
#include <queue>
#include <map>
#define maxn 200010
#define ll long long
#define INF 1000000000
using namespace std;

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

int n, a[maxn], b[maxn];

set<pair<int, int>> S, T;
map<pair<int, int>, int> id;

set<pair<int, int>> vis;
pair<int, int> ans[maxn];
void bfs() {
    queue<tuple<int, int, int, int>> Q;
    for (auto [x, y] : T) Q.push({ x, y, x, y }), vis.insert({ x, y });
    while (!Q.empty()) {
        int i, j, sx, sy; tie(i, j, sx, sy) = Q.front(); Q.pop();
        if (S.count({ i, j })) ans[id[{ i, j }]] = make_pair(sx, sy); 
        for (int k = 0; k < 4; ++k) {
            int x = i + dx[k], y = j + dy[k];
            if (vis.count({ x, y }) || !S.count({ x, y }) && !T.count({ x, y })) continue;
            vis.insert({ x, y }); Q.push({ x, y, sx, sy });
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        S.insert({ a[i], b[i] });
        id[{ a[i], b[i] }] = i;
    }
    for (int i = 1; i <= n; ++i) 
        for (int k = 0; k < 4; ++k) {
            int x = a[i] + dx[k], y = b[i] + dy[k];
            if (S.count({ x, y })) continue;
            T.insert({ x, y });
        }
    bfs();
    for (int i = 1; i <= n; ++i) cout << ans[i].first << " " << ans[i].second << "\n";
    return 0;
}