oj.uz

Submission #459572

# Submission time Handle Problem Language Result Execution time Memory
459572 2021-08-08T16:45:25 Z valerikk Iqea (innopolis2018_final_C) C++17
0 / 100
 2000 ms 58960 KB 
#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;
};

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];
vector<int> mn[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) {
		mn[i] = vector<int>(s[i].ry - s[i].ly, INF);
	}

	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;
				mn[u][pos] = min(mn[u][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;
				for (int z = 0; z < (int) mn[u].size(); ++z) {
					ans = min(ans, dist + mn[u][z] + abs(z - pos));
				}
			}
			cout << (ans == INF ? -1 : ans) << "\n";
		}
	}	
	return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19900 KB Output is correct
2 Correct 11 ms 19916 KB Output is correct
3 Correct 11 ms 19900 KB Output is correct
4 Execution timed out 2069 ms 26956 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19900 KB Output is correct
2 Correct 11 ms 19916 KB Output is correct
3 Correct 11 ms 19900 KB Output is correct
4 Execution timed out 2069 ms 26956 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 54168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 58960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19900 KB Output is correct
2 Correct 11 ms 19916 KB Output is correct
3 Correct 11 ms 19900 KB Output is correct
4 Execution timed out 2069 ms 26956 KB Time limit exceeded
5 Halted 0 ms 0 KB -