Submission #456305

#	Time	Username	Problem	Language	Result	Execution time	Memory
456305		valerikk	Iqea (innopolis2018_final_C)	C++17	20 / 100	654 ms	262148 KiB

C

#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]) {
			int nc = find_centroid(u, calc_sz(u));
			level[nc] = level[c] + 1;
			go(nc);
		}
	}
}

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

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