Submission #112991

#	Time	Username	Problem	Language	Result	Execution time	Memory
112991		model_code	Iqea (innopolis2018_final_C)	C++17	100 / 100	450 ms	36776 KiB

C

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int)1.01e9;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

void print(vector<int> a) {
	for (int x : a) printf("%d\n", x);
}

struct segtree {
	int N;
	vector<int> t;

	segtree(int n) {
		N = 1;
		while (N < n) N <<= 1;
		t.assign(2 * N, INF);
	}

	void upd(int x, int y) {
		x += N;
		while (x) {
			t[x] = min(t[x], y);
			x >>= 1;
		}
	}

	int get(int l, int r) {
		l += N;
		r += N;
		int ans = INF;
		while (l <= r) {
			if (l & 1) ans = min(ans, t[l]);
			if (!(r & 1)) ans = min(ans, t[r]);
			l = (l + 1) >> 1;
			r = (r - 1) >> 1;
		}
		return ans;
	}
};

vector<int> fast(vector<pair<int, int>> a, vector<pair<int, pair<int, int>>> b) {
	int n = a.size();
	sort(a.begin(), a.end());
	auto getId = [&](pair<int, int> o) {
		int id = lower_bound(a.begin(), a.end(), o) - a.begin();
		if (id == n || a[id] != o) return -1;
		return id;
	};
	vector<int> ans(b.size(), INF);

	vector<vector<int>> eC(n);
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < 2; k++) {
			int to = getId({ a[i].first + dx[k], a[i].second + dy[k] });
			if (to != -1) {
				eC[i].push_back(to);
				eC[to].push_back(i);
			}
		}
	}

	vector<int> c(n, -1);
	vector<vector<int>> vct;
	int m = 0;
	for (int i = 0; i < n; i++) {
		if (c[i] != -1) continue;
		vct.push_back(vector<int>());
		for (int x = a[i].first;; x++) {
			int id = getId({ x, a[i].second });
			if (id == -1) break;
			c[id] = m;
			vct[m].push_back(id);
		}
		m++;
	}

	vector<pair<int, int>> ed;
	for (int i = 0; i < n; i++) {
		int id = getId({ a[i].first, a[i].second + 1 });
		if (id != -1) {
			ed.push_back({ c[i], c[id] });
		}
	}
	sort(ed.begin(), ed.end());
	ed.resize(unique(ed.begin(), ed.end()) - ed.begin());

	vector<vector<int>> eT(m);
	for (auto o : ed) {
		eT[o.first].push_back(o.second);
		eT[o.second].push_back(o.first);
	}

	vector<char> aliveC(n, 1), aliveT(m, 1);
	vector<int> visC(n, 0), visT(m, 0);
	int tmr = 0;
	vector<int> cntT(m);
	vector<int> d(n), p(n);
	vector<int> comp(m);

	function<void(int)> dfs1 = [&](int v) {
		visT[v] = tmr;
		cntT[v] = 1;
		for (int to : eT[v]) {
			if (!aliveT[to] || visT[to] == tmr) continue;
			dfs1(to);
			cntT[v] += cntT[to];
		}
	};
	function<void(int, int)> dfs2 = [&](int v, int nw) {
		visT[v] = tmr;
		comp[v] = nw;
		for (int to : eT[v]) {
			if (!aliveT[to] || visT[to] == tmr) continue;
			dfs2(to, nw);
		}
	};
	function<void(int, vector<pair<int, int>>)> solve = [&](int v, vector<pair<int, int>> query) {
		tmr++;
		dfs1(v);
		int all = cntT[v], pr = -1;
		while (1) {
			int f = 0;
			for (int to : eT[v]) {
				if (to == pr || !aliveT[to]) continue;
				if (cntT[to] * 2 >= all) {
					f = 1;
					pr = v;
					v = to;
					break;
				}
			}
			if (!f) break;
		}
		aliveT[v] = 0;
		for (int u : vct[v]) aliveC[u] = 0;

		tmr++;
		vector<int> q;
		for (int i = 0; i < (int)vct[v].size(); i++) {
			int u = vct[v][i];
			d[u] = 0;
			p[u] = i;
			visC[u] = 0;
			q.push_back(u);
		}
		for (int qq = 0; qq < (int)q.size(); qq++) {
			int u = q[qq];
			for (int to : eC[u]) {
				if (!aliveC[to]) continue;
				if (visC[to] != tmr) {
					visC[to] = tmr;
					d[to] = INF;
				}
				if (d[to] > d[u] + 1) {
					d[to] = d[u] + 1;
					p[to] = p[u];
					q.push_back(to);
				}
			}
		}
		int k = vct[v].size();
		segtree t1(k), t2(k);
		for (auto cur : query) {
			if (b[cur.first].first == 1) {
				int u = cur.second;
				int cd = d[u], ci = p[u];
				t1.upd(ci, cd + ci);
				t2.upd(ci, cd - ci);
			}
			else {
				int u = cur.second;
				int cd = d[u], ci = p[u];
				int cres = min(t1.get(ci, k - 1) - ci, t2.get(0, ci) + ci) + cd;
				ans[cur.first] = min(ans[cur.first], cres);
			}
		}
		for (int i = 0; i < (int)eT[v].size(); i++) {
			int to = eT[v][i];
			if (!aliveT[to]) continue;
			dfs2(to, i);
		}
		vector<vector<pair<int, int>>> nq(eT[v].size());
		for (auto o : query) {
			if (c[o.second] == v) continue;
			nq[comp[c[o.second]]].push_back(o);
		}
		for (int i = 0; i < (int)eT[v].size(); i++) {
			if (nq[i].empty()) continue;
			solve(eT[v][i], nq[i]);
		}
	};
	vector<pair<int, int>> query;
	for (int i = 0; i < (int)b.size(); i++) query.push_back({ i, getId(b[i].second) });
	solve(0, query);

	for (int &x : ans) if (x > n) x = -1;
	vector<int> res;
	for (int i = 0; i < (int)b.size(); i++) if (b[i].first == 2) res.push_back(ans[i]);
	return res;
}

int main() {
	int n;
	while (scanf("%d", &n) == 1) {
		vector<pair<int, int>> a(n);
		for (int i = 0; i < n; i++) scanf("%d%d", &a[i].first, &a[i].second);
		int q;
		scanf("%d", &q);
		vector<pair<int, pair<int, int>>> b(q);
		for (int i = 0; i < q; i++) scanf("%d%d%d", &b[i].first, &b[i].second.first, &b[i].second.second);
		
		print(fast(a, b));
	}
	return 0;
}

Compilation message (stderr)

C.cpp: In function 'int main()':
C.cpp:209:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 0; i < n; i++) scanf("%d%d", &a[i].first, &a[i].second);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
C.cpp:211:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
C.cpp:213:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 0; i < q; i++) scanf("%d%d%d", &b[i].first, &b[i].second.first, &b[i].second.second);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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