#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <random>
#include <iomanip>
using namespace std;
typedef long long ll;
const int N = 100010;
const int INF = 1e9;
const int L = 20;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
int n;
int x[N], y[N];
map<pair<int, int>, int> mp;
vector<int> g[N];
int sz[N];
bool dead[N];
int level[N];
int par[N][L], dist[N][L];
vector<pair<int, int>> comp[N];
int best[N];
int calc_sz(int v, int p = -1) {
sz[v] = 1;
for (int u : g[v]) {
if (u != p && !dead[u]) {
sz[v] += calc_sz(u, v);
}
}
return sz[v];
}
int find_centroid(int v, int kek, int p = -1) {
for (int u : g[v]) {
if (u != p && !dead[u] && 2 * sz[u] > kek) {
return find_centroid(u, kek, v);
}
}
return v;
}
void dfs(int v, int c, int d = 0, int p = -1) {
comp[c].push_back({d, v});
for (int u : g[v]) {
if (u != p && !dead[u]) {
dfs(u, c, d + 1, v);
}
}
}
void go(int c) {
dfs(c, c);
dead[c] = true;
for (int u : g[c]) {
if (!dead[u]) {
level[u] = level[c] + 1;
go(find_centroid(u, calc_sz(u)));
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
//cout << x[i] << " " << y[i] << "\n";
mp[{x[i], y[i]}] = i;
}
for (int i = 0; i < n; ++i) {
for (int t = 0; t < 4; ++t) {
int nx = x[i] + dx[t], ny = y[i] + dy[t];
if (mp.count({nx, ny})) {
g[i].push_back(mp[{nx, ny}]);
}
}
}
go(find_centroid(0, calc_sz(0)));
for (int i = 0; i < n; ++i) {
best[i] = INF;
for (int j = 0; j < L; ++j) {
par[i][j] = -1;
}
}
for (int i = 0; i < n; ++i) {
for (auto [d, u] : comp[i]) {
int l = level[u] - level[i];
par[u][l] = i;
dist[u][l] = d;
}
}
int q;
cin >> q;
while (q--) {
int t, x, y;
cin >> t >> x >> y;
int v = mp[{x, y}];
if (t == 1) {
for (int i = 0; par[v][i] != -1; ++i) {
int u = par[v][i];
best[u] = min(best[u], dist[v][i]);
}
} else {
int ans = INF;
for (int i = 0; par[v][i] != -1; ++i) {
ans = min(ans, best[par[v][i]] + dist[v][i]);
}
cout << (ans == INF ? -1 : ans) << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
144 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
144 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
631 ms |
58108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
641 ms |
47732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
144 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
