Submission #459575

#	Time	Username	Problem	Language	Result	Execution time	Memory
459575		valerikk	Iqea (innopolis2018_final_C)	C++17	0 / 100	2102 ms	89652 KiB

C

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

• Subtask 1: 0 / 17
• Subtask 2: 0 / 19
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 29