#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
const int L = 20;
const int INF = 0x3f3f3f3f;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
struct Point {
int x;
int y;
};
struct Segment {
int x;
int ly;
int ry;
};
struct Item {
int dist;
int best;
int v;
};
struct SegTree {
int n;
vector<int> mn;
void upd(int pos, int val) {
int i = pos + n;
mn[i] = min(mn[i], val);
for (; i > 1; i >>= 1) {
mn[i >> 1] = min(mn[i], mn[i ^ 1]);
}
}
int get(int l, int r) {
l += n, r += n;
int res = INF;
while (l < r) {
if (l & 1) {
res = min(res, mn[l]);
++l;
}
if (r & 1) {
--r;
res = min(res, mn[r]);
}
l >>= 1, r >>= 1;
}
return res;
}
SegTree() = default;
SegTree(int n_) : n(n_) {
mn.assign(2 * n, INF);
}
};
struct SegTree2 {
int n;
SegTree t1, t2;
vector<int> mn;
void upd(int pos, int val) {
mn[pos] = min(mn[pos], val);
t1.upd(pos, mn[pos] - pos);
t2.upd(pos, mn[pos] + pos);
}
int get(int pos) {
return min(t1.get(0, pos + 1) + pos, t2.get(pos, n) - pos);
}
SegTree2() = default;
SegTree2(int n_) : n(n_), t1(n_), t2(n_) {
mn.assign(n, INF);
}
};
int n;
Point p[N];
map<pair<int, int>, int> who;
vector<int> by_x[N];
Segment s[N];
int scnt;
int id[N];
vector<int> g[N];
bool dead[N];
int sz[N];
vector<int> e[N];
bool fl[N];
pair<int, int> d[N];
int cp[N][L];
pair<int, int> cd[N][L];
vector<Item> have[N];
int lvl[N];
SegTree2 st[N];
int calc_sz(int u, int par = -1) {
for (int v : g[u]) {
if (v != par && !dead[v]) {
sz[u] += calc_sz(v, u);
}
}
return sz[u];
}
int centroid(int u, int n, int par = -1) {
for (int v : g[u]) {
if (v != par && !dead[v] && 2 * sz[v] > n) {
return centroid(v, n, u);
}
}
return u;
}
void dfs(int u, vector<int> &vs, int par = -1) {
for (int y = s[u].ly; y < s[u].ry; ++y) {
vs.push_back(who[{s[u].x, y}]);
}
for (int v : g[u]) {
if (v != par && !dead[v]) {
dfs(v, vs, u);
}
}
}
void go(int c) {
vector<int> vs;
dfs(c, vs);
for (int u : vs) {
fl[u] = true;
}
for (int u : vs) {
for (int t = 0; t < 4; ++t) {
auto it = who.find({p[u].x + dx[t], p[u].y + dy[t]});
if (it != who.end()) {
int v = it->second;
if (fl[v]) {
e[u].push_back(v);
e[v].push_back(u);
}
}
}
}
for (int u : vs) {
d[u] = {INF, -1};
}
queue<int> q;
for (int u : vs) {
if (id[u] == c) {
d[u] = {0, u};
q.push(u);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : e[u]) {
if (d[u].first + 1 < d[v].first) {
d[v] = {d[u].first + 1, d[u].second};
q.push(v);
}
}
}
for (int u : vs) {
have[c].push_back({d[u].first, d[u].second, u});
}
for (int u : vs) {
fl[u] = false;
e[u].clear();
}
dead[c] = true;
for (int u : g[c]) {
if (!dead[u]) {
int nc = centroid(u, calc_sz(u));
lvl[nc] = lvl[c] + 1;
go(nc);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> p[i].x >> p[i].y;
who[{p[i].x, p[i].y}] = i;
by_x[p[i].x].push_back(i);
}
for (int x = 0; x < N; ++x) {
sort(by_x[x].begin(), by_x[x].end(), [&](const int &i, const int &j) {
return p[i].y < p[j].y;
});
int l = -1, r = -1;
for (int i : by_x[x]) {
if (p[i].y == r) {
++r;
} else {
if (r != -1) {
s[scnt++] = {x, l, r};
}
l = p[i].y, r = p[i].y + 1;
}
}
if (r != -1) {
s[scnt++] = {x, l, r};
}
}
for (int i = 0; i < scnt; ++i) {
for (int y = s[i].ly; y < s[i].ry; ++y) {
id[who[{s[i].x, y}]] = i;
}
}
for (int i = 0; i < n; ++i) {
for (int t = 0; t < 4; ++t) {
int nx = p[i].x + dx[t], ny = p[i].y + dy[t];
if (who.count({nx, ny})) {
int j = who[{nx, ny}];
int u = id[i], v = id[j];
if (u != v) {
g[u].push_back(v);
g[v].push_back(u);
}
}
}
}
for (int i = 0; i < scnt; ++i) {
sort(g[i].begin(), g[i].end());
g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
}
go(centroid(0, calc_sz(0)));
memset(cp, 255, sizeof(cp));
for (int i = 0; i < scnt; ++i) {
for (auto it : have[i]) {
int v = it.v;
int h = lvl[id[v]] - lvl[i];
cp[v][h] = i;
cd[v][h] = {it.dist, it.best};
}
}
for (int i = 0; i < scnt; ++i) {
st[i] = SegTree2(s[i].ry - s[i].ly);
}
int q;
cin >> q;
while (q--) {
int t, x, y;
cin >> t >> x >> y;
int v = who[{x, y}];
if (t == 1) {
for (int i = 0; cp[v][i] != -1; ++i) {
int u = cp[v][i];
auto [dist, best] = cd[v][i];
int pos = p[best].y - s[u].ly;
st[u].upd(pos, dist);
}
} else {
int ans = INF;
for (int i = 0; cp[v][i] != -1; ++i) {
int u = cp[v][i];
auto [dist, best] = cd[v][i];
int pos = p[best].y - s[u].ly;
ans = min(ans, dist + st[u].get(pos));
}
cout << (ans > n ? -1 : ans) << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
26956 KB |
Output is correct |
| 2 |
Correct |
15 ms |
26976 KB |
Output is correct |
| 3 |
Correct |
15 ms |
26936 KB |
Output is correct |
| 4 |
Execution timed out |
2094 ms |
33936 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
26956 KB |
Output is correct |
| 2 |
Correct |
15 ms |
26976 KB |
Output is correct |
| 3 |
Correct |
15 ms |
26936 KB |
Output is correct |
| 4 |
Execution timed out |
2094 ms |
33936 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
587 ms |
61500 KB |
Output is correct |
| 2 |
Execution timed out |
2102 ms |
89652 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2089 ms |
65008 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
26956 KB |
Output is correct |
| 2 |
Correct |
15 ms |
26976 KB |
Output is correct |
| 3 |
Correct |
15 ms |
26936 KB |
Output is correct |
| 4 |
Execution timed out |
2094 ms |
33936 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
