Submission #846471

#	Time	Username	Problem	Language	Result	Execution time	Memory
846471		vjudge1	ČVENK (COI15_cvenk)	C++17	0 / 100	3082 ms	524288 KiB

cvenk

#include <bits/stdc++.h>
#define lint long long
#define endl '\n'
#define pii pair<int, int>
#define pll pair<lint, lint>
#define For(i,n) for (int i = 0; i < n; i++)
#define FOR For(i, n)
using namespace std;

const int N = 1e5;

map<pii, bool> vis[N];
map<pii, lint> dist;
map<pii, int> visc;

lint fdepth[N] = {};


void validpush(queue<pair<int, pair<lint, pii>>>& q, int tourist, lint depth, int x, int y) {
	if (x >= 1e9 || y >= 1e9) return;
	if (x < 0 || y < 0) return;
	if ((x & y)) return;
	if (vis[tourist][{x,y}]) return;
	q.push({tourist, {depth, {x,y}}});
}

int main() {
	int n; cin >> n;
	vector<pii> ts(n);
	for (int i = 0; i < n; i++) {
		int a,b; cin >> a >> b;
		a--; b--;
		ts[i] = {a,b};
	}

	FOR fdepth[i] = 2e18;

	// tourist, depth, x, y
	queue<pair<int, pair<lint, pair<int, int>>>> q;
	FOR q.push({i, {0ll, ts[i]}}); lint mn = 2e18;
	while (!q.empty()) {
		int tourist = q.front().first;
		lint depth = q.front().second.first;
		pii cord = q.front().second.second;
		int x = cord.first;
		int y = cord.second;
		q.pop();
		if (vis[tourist][cord]) continue;
		vis[tourist][cord] = 1;
		visc[cord]++;
		dist[cord] += depth;
		if (depth > fdepth[tourist]) {
			// no more
			continue;
		}
		if (visc[cord] == n) {
			fdepth[tourist] = depth;
			mn = min(dist[cord], mn);
			continue;
		}

		validpush(q, tourist, depth + 1, x+1, y);
		validpush(q, tourist, depth + 1, x, y+1);
		validpush(q, tourist, depth + 1, x-1, y);
		validpush(q, tourist, depth + 1, x, y-1);
	}

	cout << mn << endl;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40