oj.uz

Submission #456305

# Submission time Handle Problem Language Result Execution time Memory
456305 2021-08-06T11:36:23 Z valerikk Iqea (innopolis2018_final_C) C++17
20 / 100
 654 ms 262148 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 55392 KB Output is correct
2 Correct 545 ms 57068 KB Output is correct
3 Correct 579 ms 55640 KB Output is correct
4 Correct 654 ms 57332 KB Output is correct
5 Correct 560 ms 55696 KB Output is correct
6 Correct 538 ms 57456 KB Output is correct
7 Runtime error 351 ms 262148 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 46112 KB Output is correct
2 Correct 500 ms 48828 KB Output is correct
3 Correct 495 ms 48680 KB Output is correct
4 Correct 550 ms 49584 KB Output is correct
5 Correct 498 ms 48748 KB Output is correct
6 Correct 513 ms 48384 KB Output is correct
7 Correct 535 ms 48852 KB Output is correct
8 Correct 495 ms 48444 KB Output is correct
9 Correct 504 ms 48956 KB Output is correct
10 Correct 595 ms 53784 KB Output is correct
11 Correct 535 ms 53348 KB Output is correct
12 Correct 545 ms 54708 KB Output is correct
13 Correct 539 ms 54076 KB Output is correct
14 Correct 537 ms 52572 KB Output is correct
15 Correct 512 ms 57948 KB Output is correct
16 Correct 592 ms 56996 KB Output is correct
17 Correct 540 ms 56484 KB Output is correct
18 Correct 539 ms 55704 KB Output is correct
19 Correct 547 ms 56988 KB Output is correct
20 Correct 566 ms 54964 KB Output is correct
21 Correct 613 ms 55620 KB Output is correct
22 Correct 565 ms 54768 KB Output is correct
23 Correct 588 ms 56828 KB Output is correct
24 Correct 530 ms 55824 KB Output is correct
25 Correct 627 ms 56764 KB Output is correct
26 Correct 583 ms 56724 KB Output is correct
27 Correct 612 ms 55732 KB Output is correct
28 Correct 528 ms 56952 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -